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