前言

給定兩個(gè)遞增排序的鏈表，如何將這兩個(gè)鏈表合并？合并后的鏈表依然按照遞增排序。本文就跟大家分享一種解決方案，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。

思路分析

經(jīng)過(guò)前面的學(xué)習(xí)，我們知道了有關(guān)鏈表的操作可以用指針來(lái)完成。同樣的，這個(gè)問(wèn)題也可以用雙指針的思路來(lái)實(shí)現(xiàn)：

• p1指針指向鏈表1的頭節(jié)點(diǎn)
• p2指針指向鏈表2的頭節(jié)點(diǎn)

聲明一個(gè)變量存儲(chǔ)合并后的鏈表，比對(duì)兩個(gè)指針指向的節(jié)點(diǎn)值大小：

• 如果p1指針指向的節(jié)點(diǎn)值比p2指向的值小，合并后的鏈表節(jié)點(diǎn)就取p1節(jié)點(diǎn)的值，p1指針繼續(xù)向前走，進(jìn)行下一輪的比對(duì)。
• 如果p2指針指向的節(jié)點(diǎn)值比p1指向的值小，合并后的鏈表節(jié)點(diǎn)就取p2節(jié)點(diǎn)的值，p2指針繼續(xù)向前走，進(jìn)行下一輪的比對(duì)。
• 當(dāng)p1節(jié)點(diǎn)指向null時(shí)，合并后的鏈表節(jié)點(diǎn)就為p2所指向的鏈表節(jié)點(diǎn)；當(dāng)p2節(jié)點(diǎn)指向null時(shí)，合并后的鏈表節(jié)點(diǎn)就為p1所指向的鏈表節(jié)點(diǎn)。

實(shí)現(xiàn)代碼

看完上述分析后，聰明的開(kāi)發(fā)者已經(jīng)想到代碼怎么寫(xiě)了。沒(méi)錯(cuò)，這就是典型的遞歸思路，代碼如下：

• 聲明一個(gè)函數(shù)MergeLinkedList，它接受2個(gè)參數(shù)：遞增排序的鏈表1，遞增排序的鏈表2。
• 遞歸的基線條件：鏈表1為null就返回鏈表2，鏈表2為null就返回鏈表1。
• 聲明一個(gè)變量pMergedHead用于存儲(chǔ)合并后的鏈表頭節(jié)點(diǎn)。
• 如果當(dāng)前鏈表1的節(jié)點(diǎn)值小于鏈表2的節(jié)點(diǎn)值。

pMergedHead的值就為鏈表2的節(jié)點(diǎn)值。

pMergedHead的下一個(gè)節(jié)點(diǎn)值就為鏈表1的下一個(gè)節(jié)點(diǎn)和鏈表2的節(jié)點(diǎn)值比對(duì)后的值（遞歸）。

• 否則

pMergedHead的值就為鏈表1的節(jié)點(diǎn)值。

pMergedHead的下一個(gè)節(jié)點(diǎn)值就為鏈表2的下一個(gè)節(jié)點(diǎn)和鏈表1的節(jié)點(diǎn)值比對(duì)后的值（遞歸）。

• 最后，返回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;
}

測(cè)試用例

接下來(lái)，我們用思路分析章節(jié)中的例子來(lái)測(cè)試下我們的代碼能否正常執(zhí)行。

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);

示例代碼

本文所列舉的代碼，其完整版請(qǐng)移步：

• MergeLinkedList.ts
• MergeLinkedList-test.ts