力扣00023.合并 K 个升序链表

发表于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 9 分钟
合并 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

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

  • k == lists.length
  • $0 <= k <= 10^4$
  • 0 <= lists[i].length <= 500
  • $-10^4 <= lists[i][j] <= 10^4$
  • lists[i] 按 升序 排列
  • $lists[i].length 的总和不超过 10^4$

解决方法

C++

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }
        return mergeLists(lists, 0, lists.size() - 1);
    }
private:
    ListNode* mergeLists(std::vector<ListNode*>& lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode* l1 = mergeLists(lists, left, mid);
        ListNode* l2 = mergeLists(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) {
            return l2;
        }
        if (!l2) {
            return l1;
        }
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

结果

执行用时 : 14 ms, 击败 89.11% 使用 C++ 的用户

内存消耗 : 16.66 MB, 击败 14.97% 使用 C++ 的用户

Java

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
/**
 * 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; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return mergeLists(lists, 0, lists.length - 1);
    }
    private ListNode mergeLists(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode l1 = mergeLists(lists, left, mid);
        ListNode l2 = mergeLists(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }
    private 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;
        }
    }
}

结果

执行用时 : 2 ms, 击败 79.3% 使用 Java 的用户

内存消耗 : 43.41 MB, 击败 14.48% 使用 Java 的用户

Python

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists):
        if not lists:
            return None
        return self.merge_lists(lists, 0, len(lists) - 1)
    def merge_lists(self, lists, left, right):
        if left == right:
            return lists[left]
        mid = left + (right - left) // 2
        l1 = self.merge_lists(lists, left, mid)
        l2 = self.merge_lists(lists, mid + 1, right)
        return self.merge_two_lists(l1, l2)
    def merge_two_lists(self, l1, l2):
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val < l2.val:
            l1.next = self.merge_two_lists(l1.next, l2)
            return l1
        else:
            l2.next = self.merge_two_lists(l1, l2.next)
            return l2

结果

执行用时 : 98 ms, 击败 35.65% 使用 Python 的用户

内存消耗 : 23.25 MB, 击败 12.82% 使用 Python 的用户

Python3

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        return self.merge_lists(lists, 0, len(lists) - 1)
    def merge_lists(self, lists: List[Optional[ListNode]], left: int, right: int) -> Optional[ListNode]:
        if left == right:
            return lists[left]
        mid = left + (right - left) // 2
        l1 = self.merge_lists(lists, left, mid)
        l2 = self.merge_lists(lists, mid + 1, right)
        return self.merge_two_lists(l1, l2)
    def merge_two_lists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val < l2.val:
            l1.next = self.merge_two_lists(l1.next, l2)
            return l1
        else:
            l2.next = self.merge_two_lists(l1, l2.next)
            return l2

结果

执行用时 : 65 ms, 击败 76.55% 使用 Python3 的用户

内存消耗 : 20.19 MB, 击败 17.06% 使用 Python3 的用户

C

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.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (!l1) {
        return l2;
    }
    if (!l2) {
        return l1;
    }
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if (listsSize == 0) {
        return NULL;
    }
    if (listsSize == 1) {
        return lists[0];
    }
    int mid = listsSize / 2;
    struct ListNode* l1 = mergeKLists(lists, mid);
    struct ListNode* l2 = mergeKLists(lists + mid, listsSize - mid);
    return mergeTwoLists(l1, l2);
}

结果

执行用时 : 10 ms, 击败 97.55% 使用 C 的用户

内存消耗 : 8.04 MB, 击败 98.02% 使用 C 的用户

C#

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        if (lists == null || lists.Length == 0) {
            return null;
        }
        return MergeLists(lists, 0, lists.Length - 1);
    }
    private ListNode MergeLists(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode l1 = MergeLists(lists, left, mid);
        ListNode l2 = MergeLists(lists, mid + 1, right);
        return MergeTwoLists(l1, l2);
    }
    private 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;
        }
    }
}

结果

执行用时 : 73 ms, 击败 98.76% 使用 C# 的用户

内存消耗 : 46.32 MB, 击败 7.46% 使用 C# 的用户

JavaScript

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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if (!lists || lists.length === 0) {
        return null;
    }
    return mergeLists(lists, 0, lists.length - 1);
};
var mergeLists = function(lists, left, right) {
    if (left === right) {
        return lists[left];
    }
    var mid = left + Math.floor((right - left) / 2);
    var l1 = mergeLists(lists, left, mid);
    var l2 = mergeLists(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
};
var mergeTwoLists = function(l1, l2) {
    if (!l1) {
        return l2;
    }
    if (!l2) {
        return l1;
    }
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

结果

执行用时 : 77 ms, 击败 92.51% 使用 JavaScript 的用户

内存消耗 : 55.14 MB, 击败 11.95% 使用 JavaScript 的用户

TypeScript

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if (!lists || lists.length === 0) {
        return null;
    }
    return mergeLists(lists, 0, lists.length - 1);
}
function mergeLists(lists: Array<ListNode | null>, left: number, right: number): ListNode | null {
    if (left === right) {
        return lists[left];
    }
    const mid = left + Math.floor((right - left) / 2);
    const l1 = mergeLists(lists, left, mid);
    const l2 = mergeLists(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
}
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    if (!l1) {
        return l2;
    }
    if (!l2) {
        return l1;
    }
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

结果

执行用时 : 84 ms, 击败 95.94% 使用 TypeScript 的用户

内存消耗 : 56.80 MB, 击败 10.66% 使用 TypeScript 的用户

PHP

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
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode[] $lists
     * @return ListNode
     */
    function mergeKLists($lists) {
        if (empty($lists)) {
            return null;
        }
        return $this->mergeLists($lists, 0, count($lists) - 1);
    }
    private function mergeLists($lists, $left, $right) {
        if ($left == $right) {
            return $lists[$left];
        }
        $mid = $left + intdiv($right - $left, 2);
        $l1 = $this->mergeLists($lists, $left, $mid);
        $l2 = $this->mergeLists($lists, $mid + 1, $right);
        return $this->mergeTwoLists($l1, $l2);
    }
    private function mergeTwoLists($l1, $l2) {
        if (!$l1) {
            return $l2;
        }
        if (!$l2) {
            return $l1;
        }
        if ($l1->val < $l2->val) {
            $l1->next = $this->mergeTwoLists($l1->next, $l2);
            return $l1;
        } else {
            $l2->next = $this->mergeTwoLists($l1, $l2->next);
            return $l2;
        }
    }
}

结果

执行用时 : 21 ms, 击败 100.00% 使用 PHP 的用户

内存消耗 : 26.56 MB, 击败 27.27% 使用 PHP 的用户

Swift

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        if lists.isEmpty {
            return nil
        }
        return mergeLists(lists, 0, lists.count - 1)
    }
    private func mergeLists(_ lists: [ListNode?], _ left: Int, _ right: Int) -> ListNode? {
        if left == right {
            return lists[left]
        }
        let mid = left + (right - left) / 2
        let l1 = mergeLists(lists, left, mid)
        let l2 = mergeLists(lists, mid + 1, right)
        return mergeTwoLists(l1, l2)
    }
    private func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        guard let l1 = l1 else {
            return l2
        }
        guard let l2 = l2 else {
            return l1
        }
        if l1.val < l2.val {
            l1.next = mergeTwoLists(l1.next, l2)
            return l1
        } else {
            l2.next = mergeTwoLists(l1, l2.next)
            return l2
        }
    }
}

结果

执行用时 : 65 ms, 击败 77.22% 使用 Swift 的用户

内存消耗 : 16.79 MB, 击败 5.06% 使用 Swift 的用户

Kotlin

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
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        if (lists.isEmpty()) {
            return null
        }
        return mergeLists(lists, 0, lists.size - 1)
    }
    private fun mergeLists(lists: Array<ListNode?>, left: Int, right: Int): ListNode? {
        if (left == right) {
            return lists[left]
        }
        val mid = left + (right - left) / 2
        val l1 = mergeLists(lists, left, mid)
        val l2 = mergeLists(lists, mid + 1, right)
        return mergeTwoLists(l1, l2)
    }
    private fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        if (l1 == null) {
            return l2
        }
        if (l2 == null) {
            return l1
        }
        return if (l1.`val` < l2.`val`) {
            l1.next = mergeTwoLists(l1.next, l2)
            l1
        } else {
            l2.next = mergeTwoLists(l1, l2.next)
            l2
        }
    }
}

结果

执行用时 : 191 ms, 击败 98.00% 使用 Kotlin 的用户

内存消耗 : 37.37 MB, 击败 98.00% 使用 Kotlin 的用户

Dart

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode? next;
 *   ListNode([this.val = 0, this.next]);
 * }
 */
class Solution {
  ListNode? mergeKLists(List<ListNode?> lists) {
    if (lists.isEmpty) {
      return null;
    }
    return mergeLists(lists, 0, lists.length - 1);
  }
  ListNode? mergeLists(List<ListNode?> lists, int left, int right) {
    if (left == right) {
      return lists[left];
    }
    int mid = left + ((right - left) ~/ 2);
    ListNode? l1 = mergeLists(lists, left, mid);
    ListNode? l2 = mergeLists(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
  }
  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;
    }
  }
}

结果

执行用时 : 341 ms, 击败 71.43% 使用 Dart 的用户

内存消耗 : 149.57 MB, 击败 57.14% 使用 Dart 的用户

Go

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    return mergeLists(lists, 0, len(lists)-1)
}
func mergeLists(lists []*ListNode, left int, right int) *ListNode {
    if left == right {
        return lists[left]
    }
    mid := left + (right-left)/2
    l1 := mergeLists(lists, left, mid)
    l2 := mergeLists(lists, mid+1, right)
    return mergeTwoLists(l1, l2)
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val < l2.Val {
        l1.Next = mergeTwoLists(l1.Next, l2)
        return l1
    } else {
        l2.Next = mergeTwoLists(l1, l2.Next)
        return l2
    }
}

结果

执行用时 : 8 ms, 击败 70.42% 使用 Go 的用户

内存消耗 : 5.17 MB, 击败 22.50% 使用 Go 的用户

Ruby

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
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode[]} lists
# @return {ListNode}
def merge_k_lists(lists)
  return nil if lists.nil? || lists.empty?
  merge_lists(lists, 0, lists.length - 1)
end
def merge_lists(lists, left, right)
  return lists[left] if left == right
  mid = left + (right - left) / 2
  l1 = merge_lists(lists, left, mid)
  l2 = merge_lists(lists, mid + 1, right)
  merge_two_lists(l1, l2)
end
def merge_two_lists(l1, l2)
  return l2 if l1.nil?
  return l1 if l2.nil?
  if l1.val < l2.val
    l1.next = merge_two_lists(l1.next, l2)
    l1
  else
    l2.next = merge_two_lists(l1, l2.next)
    l2
  end
end

结果

执行用时 : 74 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 208.77 MB, 击败 -% 使用 Ruby 的用户

Scala

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
/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
  def mergeKLists(lists: Array[precompiled.ListNode]): precompiled.ListNode = {
    if (lists == null || lists.isEmpty) {
      return null
    }
    mergeLists(lists, 0, lists.length - 1)
  }
  def mergeLists(lists: Array[precompiled.ListNode], left: Int, right: Int): precompiled.ListNode = {
    if (left == right) {
      return lists(left)
    }
    val mid = left + (right - left) / 2
    val l1 = mergeLists(lists, left, mid)
    val l2 = mergeLists(lists, mid + 1, right)
    mergeTwoLists(l1, l2)
  }
  def mergeTwoLists(l1: precompiled.ListNode, l2: precompiled.ListNode): precompiled.ListNode = {
    if (l1 == null) {
      return l2
    }
    if (l2 == null) {
      return l1
    }
    if (l1.x < l2.x) { // assuming x is the field for value
      l1.next = mergeTwoLists(l1.next, l2)
      l1
    } else {
      l2.next = mergeTwoLists(l1, l2.next)
      l2
    }
  }
}

结果

执行用时 : 594 ms, 击败 75.00% 使用 Scala 的用户

内存消耗 : 58.96 MB, 击败 37.50% 使用 Scala 的用户

Rust

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Rust 的用户

内存消耗 : MB, 击败 % 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户