1. question:合并两个有序链表(简单)
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-two-sorted-lists
示例 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
| 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 = 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.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 head = mergeTwoLists(l1, l2);
while (head != null){ System.out.println(head.val); head = head.next; } } }
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)。