原题链接

题目描述:

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例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. 重新组装链表，返回头结点

golang示例代码

 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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    head := new(ListNode)
    newHead := head
    // 最笨的方法,将链表的值放入一个切片中，再排序重新组装链表
    nums := []int{}
    for i := 0; i < len(lists); i++ {
        for lists[i] != nil {
            nums = append(nums, lists[i].Val)
            lists[i] = lists[i].Next
        }
    }
    sort.Ints(nums)
    for i := 0; i < len(nums); i++ {
        node := &ListNode{Val: nums[i]}
        head.Next = node
        head = head.Next
    }
    return newHead.Next
}