【算法】链表：21.合并两个有序链表（easy）

 系列专栏

《分治》

《模拟》

《Linux》

目录

1、题目链接

2、题目介绍

3、解法（双指针）

4、代码 

1、题目链接

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

2、题目介绍

3、解法（双指针）

推荐一篇题解题解 - 力扣（LeetCode）

1. 解决方法：
   • 使用一个伪头节点来简化边界条件的处理，特别是在插入第一个节点时。这避免了处理空链表或只有一个元素的特殊情况。
   • 使用一个指针 tmp 来遍历新链表，并始终保持它指向新链表的最后一个节点，以便于进行尾插操作。
   • 遍历两个给定的链表 list1 和 list2，比较当前节点的值，将较小的节点插入到新链表中，并移动相应链表的指针到下一个节点。
   • 当其中一个链表遍历完毕后，将另一个链表剩余的节点直接连接到新链表的末尾。
2. 代码实现：
   • 初始化伪头节点 head 和临时指针 tmp。
   • 使用 while 循环遍历两个链表，直到其中一个链表为空。
     • 在循环内部，比较 list1 和 list2 当前节点的值。
     • 将值较小的节点插入到新链表中（即设置 tmp->next），并移动对应链表的指针。
     • 移动 tmp 指针到新链表的最后一个节点。
     • 
   • 使用两个额外的 while 循环来处理剩余的链表（如果有的话）。由于已经遍历过两个链表的一部分或全部，这两个循环中至多有一个会执行。
     • 这两个循环的目的是将剩余链表的所有节点连接到新链表的末尾。
   • 返回新链表的头节点（即 head->next，因为 head 是一个伪头节点）。细节很重要！！！

4、代码 

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

        ListNode* head = new ListNode(0);//初始化伪头节点，便于遍历和返回
        ListNode* tmp = head;//在新链表中，指向最后一个结点，便于实现尾插

        while (list1 != nullptr && list2 != nullptr)
        {

            if (list1->val < list2->val)
            {
                tmp->next = list1;
                list1 = list1->next;
            }
            else {
                tmp->next = list2;
                list2 = list2->next;
            }
            tmp = tmp->next;
        }
        //tmp->next = list1 != nullptr ? list1 : list2;
        while (list1 != NULL)
        {
            tmp->next = list1;
            list1 = list1->next;
            tmp = tmp->next;

        }
        while (list2 != NULL)
        {
            tmp->next = list2;
            list2 = list2->next;
            tmp = tmp->next;

        }
        return head->next;//返回真正的头节点
    }

};

💗感谢阅读！💗