WangBa's Blog

0021. Merge Two Sorted Lists

LeetCode真的难系列

发布于：2020年10月13日
次浏览

21. Merge Two Sorted Lists Easy

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example 1:

img

1
2
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

1
2
Input: l1 = [], l2 = []
Output: []

Example 3:

1
2
Input: l1 = [], l2 = [0]
Output: [0]

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both l1 and l2 are sorted in non-decreasing order.

思路：

思路一：迭代法

设置一个头结点，随后开始比较两个链表的结点值大小，具体逻辑可以将下面的图和代码逻辑联系起来：

image-20201013173854931

代码：

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
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 迭代法
    // 1 2 4     1 3 4
    // 1 1 2 3 4 4
    ListNode temp = new ListNode(-1);
    ListNode res = temp;

    while (l1 != null && l2 != null) {
        if (l1.val > l2.val) {
            temp.next = l2;
            temp = temp.next;
            l2 = l2.next;
        }
        else {
            temp.next = l1;
            temp = temp.next;
            l1 = l1.next;
        }
    }

    if (l1 == null) temp.next = l2;
    if (l2 == null) temp.next = l1;

    return res.next;

}

时间复杂度：O(m + n)

空间复杂度：O(1)

思路二：递归法

递归最重要的两个点：

  • 递归的出口，在本题里面就是当其中的一个链表为空，直接返回另外一个链表即可
  • 要进行递归，传入参数后的结果应该是已经确定的了，在这里就是链表已经排好序了

举个例子：如果现在是

1
2
3
链表la：1 -> 3 -> 5

链表lb：2 -> 4 -> 6

进行第一次递归时：要比较 1 和 2 的大小，发现 1 < 2，此时只需要将 1.next = mergeTwoLists(3, 2) 就行了，不要去想 mergeTwoLists(3, 2) 怎么来的，要把它当作已经确定的值就行，而 mergeTwoLists(3, 2) 的值可以看作是下面这两个链表的进行 mergeTwoLists 的结果

1
2
3
链表la：3 -> 5

链表lb：2 -> 4 -> 6

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 递归法
    // 递归的出口
    if (l1 == null) return l2;
    if (l2 == null) return l1;

    if (l1.val > l2.val) {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
    else {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }

}

时间复杂度：O(m + n)

空间复杂度：O(m + n)

  • 由于递归是调用栈的，每递归一次需要一个栈帧

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://wangba.me/2020/10/13/0021-Merge-Two-Sorted-Lists/

更新于：2022年3月26日

Leetcode

Array

LinkedList

评论