题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

代码展示 

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode*dummy=new ListNode(0);ListNode*current=dummy;while(list1&&list2){if(list1->val<list2->val){current->next=list1;list1=list1->next;}else{current->next=list2;list2=list2->next;}current=current->next;}if(list1){current->next=list1;}else{current->next=list2;}return dummy->next;}
};

写者心得 

current = current->next;解释

示例

假设我们有两个链表：

• list1: 1 -> 3 -> 5
• list2: 2 -> 4 -> 6

合并过程如下：

1. 初始化 dummy 和 current：

   dummy -> null
   current -> dummy

2. 第一次循环：

   • 比较 1 和 2，选择 1。
   • 连接 1 到 current 的下一个位置。
   • 移动 current 到 1。

   dummy -> 1 -> null
   current -> 1

3. 第二次循环：

   • 比较 3 和 2，选择 2。
   • 连接 2 到 current 的下一个位置。
   • 移动 current 到 2。

   dummy -> 1 -> 2 -> null
   current -> 2

4. 第三次循环：

   • 比较 3 和 4，选择 3。
   • 连接 3 到 current 的下一个位置。
   • 移动 current 到 3。

   dummy -> 1 -> 2 -> 3 -> null
   current -> 3

5. 第四次循环：

   • 比较 5 和 4，选择 4。
   • 连接 4 到 current 的下一个位置。
   • 移动 current 到 4。

   dummy -> 1 -> 2 -> 3 -> 4 -> null
   current -> 4

6. 第五次循环：

   • 比较 5 和 6，选择 5。
   • 连接 5 到 current 的下一个位置。
   • 移动 current 到 5。

   dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
   current -> 5

7. 第六次循环：

   • 比较 null 和 6，选择 6。
   • 连接 6 到 current 的下一个位置。
   • 移动 current 到 6。

   dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
   current -> 6

8. 处理剩余节点：

   • list1 已经为空，将 list2 剩余的部分连接到 current 的下一个位置。
   • 由于 list2 也已经为空，所以不需要额外操作。

9. 返回结果：

   return dummy->next;

   结果链表为：

   1 -> 2 -> 3 -> 4 -> 5 -> 6

代码的逐行解释 

创建虚拟头节点

        ListNode* dummy = new ListNode(0);ListNode* current = dummy;

• ListNode* dummy = new ListNode(0);：创建一个虚拟头节点 dummy，初始化值为0，指针为nullptr。
• ListNode* current = dummy;：创建一个指针 current，初始化指向 dummy。current 用于跟踪结果链表的当前末尾节点。

合并两个链表

        while (list1 && list2) {

• while (list1 && list2)：当 list1 和 list2 都不为空时，进入循环。

选择较小节点

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

• if (list1->val < list2->val)：比较 list1 和 list2 当前节点的值。
  • 如果 list1 的值小于 list2 的值：
    • current->next = list1;：将 list1 当前节点连接到 current 的下一个位置。
    • list1 = list1->next;：将 list1 指针移动到下一个节点。
  • 否则：
    • current->next = list2;：将 list2 当前节点连接到 current 的下一个位置。
    • list2 = list2->next;：将 list2 指针移动到下一个节点。

更新 current 指针

            current = current->next;

• current = current->next;：将 current 指针移动到刚刚连接的节点上，确保 current 始终指向结果链表的最后一个节点。

处理剩余节点

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

• if (list1)：如果 list1 不为空：
  • current->next = list1;：将 list1 剩余的部分连接到 current 的下一个位置。
• else：如果 list1 为空（即 list2 不为空）：
  • current->next = list2;：将 list2 剩余的部分连接到 current 的下一个位置。

返回结果链表的头节点

        return dummy->next;}
};

• return dummy->next;：返回结果链表的头节点。注意跳过虚拟头节点 dummy，返回 dummy->next。

总结

通过上述逐行解析，我们可以看到：

• 虚拟头节点 dummy 用于简化边界条件的处理。
• while 循环用于不断选择两个链表中较小的节点，并将其连接到结果链表中。
• if 语句用于比较两个节点的值，并选择较小的一个。
• current 指针始终指向结果链表的最后一个节点，确保下一次循环中可以继续添加新的节点。
• 最后处理剩余节点，确保所有节点都被正确连接到结果链表中。