力扣Hot100第21题——合并两个有序链表（JAVA）_java合并两个有序list

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

示例 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 均按 非递减顺序 排列

解法一迭代法
思路：创建一个新的链表，遍历list1和list2每次找到较小的一个放进新的链表里

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode h=new ListNode(-1);
        ListNode a=h; //用于记录最后返回链表的头结点
        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                h.next=list1;
                h=h.next;
                list1=list1.next;
            }
            else{
                h.next=list2;
                h=h.next;
                list2=list2.next;
            }
        }

        if(list1!=null){
            h.next=list1;
        }
        if(list2!=null){
            h.next=list2;
        }
        return a.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

解法二递归法
思路：每次找到较小的一个，将剩下的数据再进行递归比较即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1==null) return list2;
        if (list2==null) return list1;
        //如果list1.val<list2.val,那么只要修改list1.next后面的数据就可以，即在对后面的list1.next和list2重新进行递归找较小的
        if (list1.val<list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        } 
        else {
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }

    }
}
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