题目

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

示例 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、我们可能暂时还没有处理过合并k个链表，但是我们肯定很容易想象合并两个链表，那么只是把两个链表的对比横向扩展下：同时比较k个链表的头结点，加入结果链表。当然，还有后续节点则需要再次重复这个过程，直到所有链表节点都加入为止。

这个思路没有问题，剩下的就是考虑降低时间复杂度了。对于这种场景的话，比较推荐的就是堆排序了。(刷题解会看到优先队列的思路，其实是一个道理)

2、继续沿着合并两个链表的思路去想，把k个链表的合并拆分成一个又一个的两个链表合并即可。同样的需要考虑时间复杂度的优化，那就是采用分治的方式，两两合并，最终合并成为结果。

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// 分治方法
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) <= 0 {
        return nil
    }
    return merge(lists, 0, len(lists)-1)
}

func merge(lists []*ListNode, left, right int) *ListNode {
    if left == right {
        return lists[left]
    }
    mid := (left + right) / 2
    return mergeTwo(merge(lists, left, mid), merge(lists, mid + 1, right))
}

func mergeTwo(a, b *ListNode) *ListNode {
    if a == nil {
        return b
    }
    if b == nil {
        return a
    }
    veryHead := &ListNode{}
    head := veryHead
    for a != nil || b != nil {
        if a == nil {
            head.Next = b
            b = b.Next
        } else if b == nil {
            head.Next = a
            a = a.Next
        } else if a.Val > b.Val {
            head.Next = b
            b = b.Next
        } else {
            head.Next = a
            a = a.Next
        }
        head = head.Next
    }
    return veryHead.Next
}

// 最小堆方法
func mergeKLists(lists []*ListNode) *ListNode {
	h := hp{}
	for _, head := range lists {
		if head != nil {
			h = append(h, head)
		}
	}
	// 堆化
	heap.Init(&h)

	veryHead := &ListNode{}
	now := veryHead
	for len(h) > 0 {
		// 初始化之后，堆顶为最小值
		node := heap.Pop(&h).(*ListNode)
		if node.Next != nil {
			// 如果有下个节点，继续入堆，会自动调整，保持堆顶为最小
			heap.Push(&h, node.Next)
		}
		now.Next = node
		now = now.Next
	}
	return veryHead.Next
}

type hp []*ListNode

func (h hp) Len() int {
	return len(h)
}
func (h hp) Less(i, j int) bool {
	return h[i].Val < h[j].Val
}
func (h hp) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
func (h *hp) Push(v interface{}) {
	*h = append(*h, v.(*ListNode))
}
func (h *hp) Pop() interface{} {
	a := *h
	v := a[len(a)-1]
	*h = a[:len(a)-1]
	return v
}

看到这里了，点个赞点个在看呗！~ 多谢啦！~

半亩房顶

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

题目

思路

代码

LeetCode-92. 反转链表 II