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

目录

题目

合并两个有序链表的思路

读者可能的错误写法

正确的写法

题目

21. 合并两个有序链表 - 力扣（LeetCode）

合并两个有序链表的思路

处理边界情况：

• 如果list1为空，直接返回list2

• 如果list2为空，直接返回list1

使用哨兵节点：

• 创建一个哨兵节点dummy(值为0)作为合并链表的起点

• 使用一个current指针跟踪当前合并位置

合并过程：

• 同时遍历两个链表，比较当前节点的值

• 将较小值的节点连接到current的next

• 移动较小值所在的链表指针和current指针

• 重复这个过程直到其中一个链表遍历完毕

处理剩余节点：

• 当其中一个链表遍历完成后，将另一个链表的剩余部分直接连接到current的next

• 这是有效的，因为剩余部分已经是有序的

返回结果：

• 返回dummy->next作为合并后的链表头

• 释放dummy节点以避免内存泄漏

时间和空间复杂度

• 时间复杂度：O(m+n)，其中m和n分别是两个链表的长度

• 空间复杂度：O(1)，只使用了常数额外空间

读者可能的错误写法

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

        while(list1)
        {
                newhead = list1;
                list1 = list1->next;
                newhead = newhead->next;
        }
        while(list2)
        {
                newhead = list2;
                list2 = list2->next; 
                newhead = newhead->next;
        }

        return newhead;
    }
};

上面代码有一些错误

空指针检查：

• 没有检查list1或list2是否为nullptr，直接访问list1->val和list2->val会导致空指针错误

哨兵节点使用错误：

• 创建了dummy节点但没有正确使用

• newhead = dummy->next是错误的，因为dummy->next初始为nullptr

• 没有通过dummy构建链表

节点连接逻辑错误：

• 没有正确连接节点，只是将newhead指向不同节点

• newhead = newhead->next会导致丢失之前的节点

返回值错误：

• 最终返回newhead，但这可能是nullptr或指向链表末尾

正确的写法

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

        //while(list1) //这种写法也对，但是太麻烦了
        //{
                //cur->next = list1;
                //list1 = list1->next;
                //cur = cur->next;
        //}
        //while(list2)
        //{
                //cur->next = list2;
                //list2 = list2->next; 
                //cur = cur->next;
        //}

        if (list1)
        {
            current->next = list1;
        } 
        if (list2)
        {
            current->next = list2;
        } 
        

        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};