23. 合并K个排序链表（困难）

• 难度: 困难
• 考察: 链表
• 来源: https://leetcode-cn.com/problems/merge-k-sorted-lists/
• 题解: https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0023-Merge-k-Sorted-Lists/Article/0023-Merge-k-Sorted-Lists.md
• 题解: https://github.com/azl397985856/leetcode/blob/master/problems/23.merge-k-sorted-lists.md
• 题解: https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/

题目

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路

暴力合并

1. 循环k个链表，找到最小数m，将m从原链表移动到结果列表ans
2. 循环步骤1，直到k个链表的元素全部移动到ans

顺序合并

k个链表依次合并到结果链表ans

分治合并

1. k个链表两两合并
2. 合并的结果继续两两合并，直到只剩一个结果链表ans

关键点

• 有序链表

复杂度

• 时间复杂度：O(K*N)
• 空间复杂度：O(1)

代码

暴力合并

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
	var head, node *ListNode
	for {
		min := -1
		for i := 0; i < len(lists); i++ {
			if lists[i] == nil {
				continue
			}
			if min == -1 || lists[min].Val > lists[i].Val {
				min = i
			}
		}
		if min == -1 {
			break
		}
		if head == nil {
			head = lists[min]
			node = lists[min]
		} else {
			node.Next = lists[min]
			node = node.Next
		}
		lists[min] = lists[min].Next
	}
	return head
}