题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
我的解答
两个技巧
- 双指针分别在两个链表上移动对比
- 新链表使用虚拟头创建（降低空链表初始化时候的复杂度）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode p = dummy, p1=list1,p2=list2;
while(p1 != null && p2 != null){
if(p1.val > p2.val){
p.next = p2;
p2 = p2.next;
}else{
p.next = p1;
p1 = p1.next;
}
p = p.next;
}
if(p1 == null){
p.next = p2;
}
if(p2 == null){
p.next = p1;
}
return dummy.next;
}
|
官方参考
递归直接拼接链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
|
链接：https://leetcode.cn/problems/merge-two-sorted-lists/