LeetCode-23.合并 K 个升序链表

链表#

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

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

示例 1：

1
输入：lists = [[1,4,5],[1,3,4],[2,6]]
2
输出：[1,1,2,3,4,4,5,6]
3
解释：链表数组如下：
4
[
5
  1->4->5,
6
  1->3->4,
7
  2->6
8
]
9
将它们合并到一个有序链表中得到。
10
1->1->2->3->4->4->5->6

示例 2：

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

示例 3：

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

自己的解法(照抄148. 排序链表)

也算是手撕吧…

1
/**
2
 * Definition for singly-linked list.
3
 * type ListNode struct {
4
 *     Val int
5
 *     Next *ListNode
6
 * }
7
 */
8
func mergeKLists(lists []*ListNode) *ListNode {
9
    filtered := make([]*ListNode, 0, len(lists))
10
    for _, l := range lists {
11
        if l != nil {
12
            filtered = append(filtered, l)
13
        }
14
    }
15
    if len(filtered) == 0 {
16
        return nil
17
    }
18
    if len(filtered) == 1 {
19
        return filtered[0]
20
    }
21

22
    for i := 0; i < len(filtered)-1; i++ {
23
        cur := filtered[i]
24
        for cur.Next != nil {
25
            cur = cur.Next
26
        }
27
        cur.Next = filtered[i+1]
28
    }
29

30
    return sortList(filtered[0])
31
}
32

33
func sortList(head *ListNode) *ListNode {
34
    if head == nil || head.Next == nil {
35
        return head
36
    }
37

38
    slow, fast := head, head.Next
39
    for fast != nil && fast.Next != nil {
40
        slow = slow.Next
41
        fast = fast.Next.Next
42
    }
43

44
    mid := slow.Next
45
    slow.Next = nil
46

47
    left := sortList(head)
48
    right := sortList(mid)
49

50
    return mergeTwoLists(left, right)
51
}
52

53
func mergeTwoLists(list1, list2 *ListNode) *ListNode {
54
    dummy := &ListNode{}
55
    cur := dummy
56

57
    for list1 != nil && list2 != nil {
58
        if list1.Val < list2.Val {
59
            cur.Next = list1
60
            list1 = list1.Next
61
        } else {
62
            cur.Next = list2
63
            list2 = list2.Next
64
        }
65
        cur = cur.Next
66
    }
67

68
    if list1 != nil {
69
        cur.Next = list1
70
    } else {
71
        cur.Next = list2
72
    }
73

74
    return dummy.Next
75
}

更合适的解法

思路：这里的思路与 148. 排序链表 稍有不同，上一题是把一个链表化为多个长度为一的链表，这里lists我们把切片的每一个元素提取，所以需要divideAndMerge。

其中，divideAndMerge本质就是对一串数字进行操作，如果只剩一个数字，就进行mergeTwoLists,后面的逻辑就是和排序链表差不多了。

1
/**
2
 * Definition for singly-linked list.
3
 * type ListNode struct {
4
 *     Val int
5
 *     Next *ListNode
6
 * }
7
 */
8
func mergeKLists(lists []*ListNode) *ListNode {
9
    if len(lists) == 0 {
10
        return nil
11
    }
12
    return divideAndMerge(lists, 0, len(lists)-1)
13
}
14

15
func divideAndMerge(lists []*ListNode, left, right int) *ListNode {
16
    if left == right {
17
        return lists[left]
18
    }
19

20
    mid := left + (right - left) / 2
21

22
    l1 := divideAndMerge(lists, left, mid)
23
    l2 := divideAndMerge(lists, mid+1, right)
24

25
    return mergeTwoLists(l1, l2)
26
}
27

28
func mergeTwoLists(list1, list2 *ListNode) *ListNode {
29
    dummy := &ListNode{}
30
    cur := dummy
31

32
    for list1 != nil && list2 != nil {
33
        if list1.Val < list2.Val {
34
            cur.Next = list1
35
            list1 = list1.Next
36
        } else {
37
            cur.Next = list2
38
            list2 = list2.Next
39
        }
40
        cur = cur.Next
41
    }
42
    if list1 != nil {
43
        cur.Next = list1
44
    } else {
45
        cur.Next = list2
46
    }
47
    return dummy.Next
48
}