给定两个递增排序的链表，如何将这两个链表合并？合并后的链表依然按照递增排序。本文就跟大家分享一种解决方案
经过前面的学习，我们知道了有关链表的操作可以用指针来完成。同样的，这个问题也可以用双指针的思路来实现：
声明一个变量存储合并后的链表，比对两个指针指向的节点值大小：
看完上述分析后，聪明的开发者已经想到代码怎么写了。没错，这就是典型的递归思路，代码如下：
1.声明一个函数MergeLinkedList，它接受2个参数：递增排序的链表1，递增排序的链表2
2.递归的基线条件：链表1为null就返回链表2，链表2为null就返回链表1
3.声明一个变量pMergedHead用于存储合并后的链表头节点
4.如果当前链表1的节点值小于链表2的节点值
5.否则
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);
