链表

递归

# 递归

# lc21. 合并两个有序的链表简单top

题目描述

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

示例 1：

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

1
2

示例 2：

输入：l1 = [], l2 = []
输出：[]

1
2

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

1
2

法一：递归

思路：

从链表头开始，l1和l2是有序递增的链表，比较l1.val和l2.val的较小值就是合并后链表的最小值，次小值就是小节点的next.val和大节点val比较的小值，依次递归到l1和l2均为null

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, 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(l2.next, l1)
        return l2
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

法二：虚拟节点和迭代

这种方法比较容易理解一点!

创建一个新的链表preHead，然后对l1和l2进行判空的while循环
然后比较val的大小
然后接在preHead后面
最后返回preHead的头结点s

var mergeTwoLists = function(l1, l2) {
    
    let preHead = new ListNode(-1);
    let cur = preHead;

    while(l1 && l2){
        if(l1.val < l2.val){
            cur.next = l1;
            l1 = l1.next;
        }else{
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }

    cur.next = l1 || l2;

    return preHead.next;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# lc23. 合并`K`个升序链表困难

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]

输出：[1,1,2,3,4,4,5,6]

解释：链表数组如下：

[

  1->4->5,

  1->3->4,

  2->6

]

将它们合并到一个有序链表中得到。

1->1->2->3->4->4->5->6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

示例 2：

输入：lists = []

输出：[]

1
2
3
4
5

示例 3：

输入：lists = [[]]

输出：[]

1
2
3
4
5

思路同上面合并两个链表相同

var mergeKLists = function(lists) {
  let res = null
  for(let i = 0;i < lists.length; i++) {
    res = mergeTwoList(res, lists[i])
  }
  return res
};

var mergeTwoList = function(l1, l2) {
  let dummyHead = new ListNode(null)
  let cur = dummyHead

  while(l1 && l2) {
    if(l1.val < l2.val) {
      cur.next = l1
      l1 = l1.next
    } else {
      cur.next = l2
      l2 = l2.next
    }
    cur = cur.next
  }
  cur.next = l1 || l2
  return dummyHead.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

时间复杂度：O(NlogK)，K 条链表的总结点数是 N，平均每条链表有 N/K 个节点，因此合并两条链表的时间复杂度是 O(N/K)。

从 K 条链表开始两两合并成一条链表，因此每条链表都会被合并 logK、次，因此 K条链表会被合并 K * logK 次，因此总共的时间复杂度是 K * logK * N/K 即 O(NlogK)

空间复杂度O(1)

上次更新: 2022/02/19, 22:25:17

快慢指针→

递归

# 递归

# lc21. 合并两个有序的链表简单top

# lc23. 合并K个升序链表困难

# lc23. 合并`K`个升序链表困难