23. 合并 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

解法一：顺序合并

 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


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    var mergeTowLists func(a, b *ListNode)*ListNode
    mergeTowLists = func(a, b *ListNode) *ListNode{
        dummy := &ListNode{}
        tail := dummy
        for a != nil && b!=nil {
            if a.Val < b.Val {
                tail.Next = a
                a=a.Next
            } else {
                tail.Next = b
                b = b.Next
            }
            tail = tail.Next
        }
        if a != nil {
            tail.Next = a
        } else {
            tail.Next = b
        }
        return dummy.Next
    }
    var ans *ListNode
    for _, list := range lists {
        ans = mergeTowLists(ans, list)
    }
    return ans
}

解法二：分治合并

 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 {
    n := len(lists)
    if n == 0 {
        return nil
    } else if n == 1 {
        return lists[0]
    } else {
        mid := n / 2
        listA := mergeKLists(lists[0:mid])
        listB := mergeKLists(lists[mid:n])
        dummy := &ListNode{}
        tail := dummy
        for listA != nil && listB != nil {
            if listA.Val < listB.Val {
                tail.Next = listA
                listA = listA.Next
            } else {
                tail.Next = listB
                listB = listB.Next
            }
            tail = tail.Next
        }
        if listA != nil {
            tail.Next = listA
        } else {
            tail.Next = listB
        }
        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
51
52
53


type PriorityQueue struct {
    arr []*ListNode
}

func (pq *PriorityQueue) Less(i, j int) bool {
    return pq.arr[i].Val < pq.arr[j].Val
}

func (pq *PriorityQueue) Push(node interface{}) {
    pq.arr = append(pq.arr, node.(*ListNode))
}

func (pq *PriorityQueue) Pop() interface{} {
    a := pq.arr
    ret := a[len(a)-1]
    pq.arr = a[:len(a)-1]
    return ret
}

func (pq *PriorityQueue) Swap(i, j int) {
    pq.arr[i], pq.arr[j] = pq.arr[j], pq.arr[i]
}

func (pq *PriorityQueue) Len() int {
    return len(pq.arr)
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    pq := &PriorityQueue{}
    for _, list := range lists {
        if list != nil {
            heap.Push(pq, list)
        }
    }
    dummy := &ListNode{}
    tail := dummy
    for pq.Len() > 0 {
        top := heap.Pop(pq)
        tail.Next = top.(*ListNode)
        tail = tail.Next
        if tail.Next != nil {
            heap.Push(pq, tail.Next)
        }
    }
    return dummy.Next
}