聊一聊合并兩個排序的鏈表
作者：神奇的程序員
當p1節點指向null時，合并后的鏈表節點就為p2所指向的鏈表節點；當p2節點指向null時，合并后的鏈表節點就為p1所指向的鏈表節點。
前言
給定兩個遞增排序的鏈表，如何將這兩個鏈表合并？合并后的鏈表依然按照遞增排序。本文就跟大家分享一種解決方案，歡迎各位感興趣的開發者閱讀本文。
思路分析
經過前面的學習，我們知道了有關鏈表的操作可以用指針來完成。同樣的，這個問題也可以用雙指針的思路來實現：
- p1指針指向鏈表1的頭節點
- p2指針指向鏈表2的頭節點
聲明一個變量存儲合并后的鏈表，比對兩個指針指向的節點值大小：
- 如果p1指針指向的節點值比p2指向的值小，合并后的鏈表節點就取p1節點的值，p1指針繼續向前走，進行下一輪的比對。
- 如果p2指針指向的節點值比p1指向的值小，合并后的鏈表節點就取p2節點的值，p2指針繼續向前走，進行下一輪的比對。
- 當p1節點指向null時，合并后的鏈表節點就為p2所指向的鏈表節點；當p2節點指向null時，合并后的鏈表節點就為p1所指向的鏈表節點。
實現代碼
看完上述分析后，聰明的開發者已經想到代碼怎么寫了。沒錯，這就是典型的遞歸思路，代碼如下：
- 聲明一個函數MergeLinkedList，它接受2個參數：遞增排序的鏈表1，遞增排序的鏈表2。
- 遞歸的基線條件：鏈表1為null就返回鏈表2，鏈表2為null就返回鏈表1。
- 聲明一個變量pMergedHead用于存儲合并后的鏈表頭節點。
- 如果當前鏈表1的節點值小于鏈表2的節點值。
pMergedHead的值就為鏈表2的節點值。
pMergedHead的下一個節點值就為鏈表1的下一個節點和鏈表2的節點值比對后的值（遞歸）。
- 否則
pMergedHead的值就為鏈表1的節點值。
pMergedHead的下一個節點值就為鏈表2的下一個節點和鏈表1的節點值比對后的值（遞歸）。
- 最后，返回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
- MergeLinkedList-test.ts
責任編輯：武曉燕
來源：
神奇的程序員
