LeetCode - 21. 合并两个有序链表

题目

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