TypeScript合并排序链表
神奇的程序员 人气:0前言
给定两个递增排序的链表,如何将这两个链表合并?合并后的链表依然按照递增排序。本文就跟大家分享一种解决方案
思路分析
经过前面的学习,我们知道了有关链表的操作可以用指针来完成。同样的,这个问题也可以用双指针的思路来实现:
- p1指针指向链表1的头节点
- p2指针指向链表2的头节点
声明一个变量存储合并后的链表,比对两个指针指向的节点值大小:
- 如果p1指针指向的节点值比p2指向的值小,合并后的链表节点就取p1节点的值,p1指针继续向前走,进行下一轮的比对
- 如果p2指针指向的节点值比p1指向的值小,合并后的链表节点就取p2节点的值,p2指针继续向前走,进行下一轮的比对
- 当p1节点指向null时,合并后的链表节点就为p2所指向的链表节点;当p2节点指向null时,合并后的链表节点就为p1所指向的链表节点。
实现代码
看完上述分析后,聪明的开发者已经想到代码怎么写了。没错,这就是典型的递归思路,代码如下:
1.声明一个函数MergeLinkedList,它接受2个参数:递增排序的链表1,递增排序的链表2
2.递归的基线条件:链表1为null就返回链表2,链表2为null就返回链表1
3.声明一个变量pMergedHead
用于存储合并后的链表头节点
4.如果当前链表1的节点值小于链表2的节点值
- pMergedHead的值就为链表2的节点值
- pMergedHead的下一个节点值就为链表1的下一个节点和链表2的节点值比对后的值(递归)
5.否则
- pMergedHead的值就为链表1的节点值
- pMergedHead的下一个节点值就为链表2的下一个节点和链表1的节点值比对后的值(递归)
6.最后,返回pMergedHead
export function MergeLinkedList( firstListHead: ListNode | null, secondListHead: ListNode | null ): ListNode | null { // 基线条件 if (firstListHead == null) { return secondListHead; } if (secondListHead == null) { return firstListHead; } let pMergedHead: ListNode | null = null; if (firstListHead.element < secondListHead.element) { pMergedHead = firstListHead; pMergedHead.next = MergeLinkedList(firstListHead.next, secondListHead); } else { pMergedHead = secondListHead; pMergedHead.next = MergeLinkedList(firstListHead, secondListHead.next); } return pMergedHead; }
测试用例
接下来,我们用思路分析章节中的例子来测试下我们的代码能否正常执行。
const firstLinkedList = new LinkedList(); firstLinkedList.push(1); firstLinkedList.push(3); firstLinkedList.push(5); firstLinkedList.push(7); firstLinkedList.push(9); const secondLinkedList = new LinkedList(); secondLinkedList.push(2); secondLinkedList.push(4); secondLinkedList.push(6); secondLinkedList.push(8); const resultListHead = MergeLinkedList( firstLinkedList.getHead(), secondLinkedList.getHead() ); console.log(resultListHead);
示例代码
本文所列举的代码如下
MergeLinkedList.ts
import { ListNode } from "./utils/linked-list-models.ts"; /** * 合并两个排序的链表 * 1. p1指针指向链表1,p2指针指向链表2 * 2. 递归比对指针指向的两个值,构造新的链表 * @param firstListHead 链表1 * @param secondListHead 链表2 * @constructor */ export function MergeLinkedList( firstListHead: ListNode | null, secondListHead: ListNode | null ): ListNode | null { // 基线条件 if (firstListHead == null) { return secondListHead; } if (secondListHead == null) { return firstListHead; } let pMergedHead: ListNode | null = null; if (firstListHead.element < secondListHead.element) { pMergedHead = firstListHead; pMergedHead.next = MergeLinkedList(firstListHead.next, secondListHead); } else { pMergedHead = secondListHead; pMergedHead.next = MergeLinkedList(firstListHead, secondListHead.next); } return pMergedHead; }
MergeLinkedList-test.ts
import { MergeLinkedList } from "../MergeLinkedList.ts"; import LinkedList from "../lib/LinkedList.ts"; const firstLinkedList = new LinkedList(); firstLinkedList.push(1); firstLinkedList.push(3); firstLinkedList.push(5); firstLinkedList.push(7); firstLinkedList.push(9); const secondLinkedList = new LinkedList(); secondLinkedList.push(2); secondLinkedList.push(4); secondLinkedList.push(6); secondLinkedList.push(8); const resultListHead = MergeLinkedList( firstLinkedList.getHead(), secondLinkedList.getHead() ); console.log(resultListHead);
加载全部内容