题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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
合并过程如下:
-
初始化
dummy
和current
:dummy -> null current -> dummy
-
第一次循环:
- 比较
1
和2
,选择1
。 - 连接
1
到current
的下一个位置。 - 移动
current
到1
。
dummy -> 1 -> null current -> 1
- 比较
-
第二次循环:
- 比较
3
和2
,选择2
。 - 连接
2
到current
的下一个位置。 - 移动
current
到2
。
dummy -> 1 -> 2 -> null current -> 2
- 比较
-
第三次循环:
- 比较
3
和4
,选择3
。 - 连接
3
到current
的下一个位置。 - 移动
current
到3
。
dummy -> 1 -> 2 -> 3 -> null current -> 3
- 比较
-
第四次循环:
- 比较
5
和4
,选择4
。 - 连接
4
到current
的下一个位置。 - 移动
current
到4
。
dummy -> 1 -> 2 -> 3 -> 4 -> null current -> 4
- 比较
-
第五次循环:
- 比较
5
和6
,选择5
。 - 连接
5
到current
的下一个位置。 - 移动
current
到5
。
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null current -> 5
- 比较
-
第六次循环:
- 比较
null
和6
,选择6
。 - 连接
6
到current
的下一个位置。 - 移动
current
到6
。
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null current -> 6
- 比较
-
处理剩余节点:
list1
已经为空,将list2
剩余的部分连接到current
的下一个位置。- 由于
list2
也已经为空,所以不需要额外操作。
-
返回结果:
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
指针始终指向结果链表的最后一个节点,确保下一次循环中可以继续添加新的节点。- 最后处理剩余节点,确保所有节点都被正确连接到结果链表中。