LeetCode_07_MergeTwoSortedLists


1. question:合并两个有序链表(简单)

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-two-sorted-lists

示例 1:

示例1

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

示例 2:

1
2
输入:l1 = [], l2 = []
输出:[]

示例 3:

1
2
输入:l1 = [], l2 = [0]
输出:[0]

提示:

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

2. answer

思路:

该题比较简单,直接比较即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//Definition for singly-linked list.
class ListNodes {
int val;
ListNodes next;
ListNodes() {}
ListNodes(int val) { this.val = val; }
ListNodes(int val, ListNodes next) { this.val = val; this.next = next; }
}

public class Solution_0007 {

public static ListNodes mergeTwoLists(ListNodes list1, ListNodes list2) {

ListNodes head = new ListNodes();
ListNodes temp = head;

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

if(list1.val >= list2.val){
temp.next = list2;
list2 = list2.next;
} else {
temp.next = list1;
list1 = list1.next;
}

temp = temp.next;
}

temp.next = list1 == null ? list2 : list1;

return head.next;
}

public static void main(String[] args) {

// ListNodes l1 = new ListNodes(1);
// ListNodes tempL1 = l1;
// tempL1.next = new ListNodes(2);
// tempL1 = tempL1.next;
// tempL1.next = new ListNodes(4);
//
// ListNodes l2 = new ListNodes(1);
// ListNodes tempL2 = l2;
// tempL2.next = new ListNodes(3);
// tempL2 = tempL2.next;
// tempL2.next = new ListNodes(4);


// ListNodes l1 = null;
//
// ListNodes l2 = new ListNodes(0);

ListNodes l1 = null;
ListNodes l2 = null;

ListNodes head = mergeTwoLists(l1, l2);

while (head != null){
System.out.println(head.val);
head = head.next;
}

}
}

递归的方法:即下一次合并的是 链表中 去掉 当前已知节点剩余的 部分 和 另一个链表。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Solution_0007_02 {
public static ListNodes mergeTwoLists(ListNodes list1, ListNodes list2) {

// 有一条链表为空,直接链接另一条链表即可。
if(list1 == null) {
return list2;
} else if(list2 == null){
return list1;
} else {

// 两条链表均为非空,那么就比较元素
if(list1.val < list2.val){
// list1节点比较小,也就是它放在前面,那么返回结果中的它之后的链表怎么计算呢?
// 就是list1所在链表剩余的链表和list2链表进行合并后的链表,递归调用该方法。
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
// 同上
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}

public static void main(String[] args) {
ListNodes l1 = new ListNodes(1);
ListNodes tempL1 = l1;
tempL1.next = new ListNodes(2);
tempL1 = tempL1.next;
tempL1.next = new ListNodes(4);

ListNodes l2 = new ListNodes(1);
ListNodes tempL2 = l2;
tempL2.next = new ListNodes(3);
tempL2 = tempL2.next;
tempL2.next = new ListNodes(4);


// ListNodes l1 = null;
//
// ListNodes l2 = new ListNodes(0);

// ListNodes l1 = null;
// ListNodes l2 = null;

ListNodes head = mergeTwoLists(l1, l2);

while (head != null){
System.out.println(head.val);
head = head.next;
}
}
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录