題目

21. 合并兩個有序鏈表

思路

我會采用雙指針的方法，同時遍歷兩個鏈表，比較當前節點的值，將較小的節點添加到結果鏈表中。

具體思路是這樣的：

首先創建一個啞節點(dummy node)作為合并后鏈表的頭部，這樣可以簡化邊界情況的處理

用兩個指針分別指向兩個鏈表的當前節點

比較兩個指針所指節點的值，將值較小的節點添加到結果鏈表，并將對應的指針向后移動

重復步驟3，直到其中一個鏈表遍歷完畢

將另一個還有剩余的鏈表直接接到結果鏈表后面

返回dummy.next作為合并后的鏈表頭

讀者可能出現的錯誤

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* p1 = list1;ListNode* p2 = list2;ListNode* dummy = new ListNode(0);ListNode* cur = dummy;while(p1&&p2){if(p1->val >= p2->val){cur->next = p2;p2 = p2->next;}else{cur->next = p1;p1 = p1->next;}}if(p1){cur->next = p1;}else{cur->next = p2;}ListNode* newlist = cur;delete dummy;return newlist;}
};

沒有更新cur指針：在每次連接節點后，沒有執行cur = cur->next，導致cur一直停留在dummy節點，每次操作都會覆蓋之前的連接。

當把后續的鏈表添加上的時候應該用while，而不是用if

返回值錯誤：應該返回dummy->next（合并后的鏈表頭），而不是cur或newlist。

正確的代碼

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* p1 = list1;ListNode* p2 = list2;ListNode* dummy = new ListNode(0);ListNode* cur = dummy;while(p1 && p2){if(p1->val >= p2->val){cur->next = p2;p2 = p2->next;}else{cur->next = p1;p1 = p1->next;}cur = cur->next;}while(p1){cur->next = p1;p1 = p1->next;cur = cur->next;}while(p2){cur->next = p2;p2 = p2->next;cur = cur->next;}ListNode* newhead = dummy->next;delete dummy;return newhead;}
};