题目

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

示例1：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路1

分为两步：

第一步： 记录所有的链表的数值并排序。因为链表的长度未知，所以需要用 List 来存储。

第二步： 按照排序后的链表数值，建立对应链表。

代码

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null&&l2==null) return null;
        if(l1!=null&&l2==null) return l1;
        if(l1==null&&l2!=null) return l2;
        List<Integer> list = new ArrayList<>();
        while(l1!=null){
            list.add(l1.val);
            l1=l1.next;
        }
        while(l2!=null){
            list.add(l2.val);
            l2=l2.next;
        }
        Collections.sort(list);
        int size = list.size();
        ListNode result = new ListNode(list.get(0).intValue());
        ListNode pev = result;
        for(int i=1;i<size;i++){
            ListNode tmp = new ListNode(list.get(i).intValue());
            pev.next = tmp;
            pev = tmp;
        }
        return result;
    }
}

思路2

官方题解：采用递归方法。

终止条件：l1 = null 或者 l2 = null。

判断条件：
if(l1.val<l2.val): mergeTwoLists(l1.next, l2)
else: mergeTwoLists(l1, l2.next)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        if(l1.val<l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

思路3

官方题解：采用递归。

时间复杂度与空间复杂度最优。

关键在于设计哨兵节点，记录前一个节点。

代码

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode preHead = new ListNode(-1);
        ListNode preNode = preHead;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                preNode.next = l1;
                l1 = l1.next;
            }else{
                preNode.next = l2;
                l2 = l2.next;
            }
            preNode = preNode.next;
        }
        preNode.next = l1==null?l2:l1;
        return preHead.next;
    }
}