1
 2
 3
 4
 5
 6
 7
 8
 9
10

输入：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

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

1
2

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

 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:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        size = len(lists)
        if size == 0:
            return None
        if size == 1:
            return lists[0]

        l1 = lists[0]
        l2 = self.mergeKLists(lists[1:])

        dummy = p = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                p.next = l1
                l1 = l1.next
            else:
                p.next = l2
                l2 = l2.next
            p = p.next
        if l1:
            p.next = l1
        elif l2:
            p.next = l2

        return dummy.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
37
38
39
40
41
42
43
44
45
46
47
48
49
50

// @lc code=start
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    /// ## 解题思路
    /// - 递归
    /// 1. k == 0, 返回None;
    /// 2. k == 1, 返回lists[0];
    /// 3. k > 1, 返回将lists对半切开,分别合并后,再将两者合并;
    pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        fn merge_list(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>>{
            match (list1, list2) {
                (None, None) => None,
                (None, Some(list2)) => Some(list2),
                (Some(list1), None) => Some(list1),
                (Some(mut list1), Some(mut list2)) => {
                    if list1.val < list2.val {
                        list1.next = merge_list(list1.next.take(), Some(list2));
                        Some(list1)
                    } else {
                        list2.next = merge_list(Some(list1), list2.next.take());
                        Some(list2)
                    }
                }
            }
        }
        match lists.len() {
            0 => None,
            1 => lists[0].clone(),
            l => {
                merge_list(Self::merge_k_lists(lists[0..l/2].to_vec()), Self::merge_k_lists(lists[l/2..].to_vec()))
            }
        }
    }
}
// @lc code=end