leetcode-合并K个排序链表

一、题目

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

二、思路一

分治法两两合并

• 将k个链表配对并将同一对中的链表合并
• 第一轮合并后，k个链表被合并成了$\frac{k}{2}$ 个链表，平均长度为$\frac{2n}{k}$，总共n个元素。然后是$\frac{k}{4}$个链表，$\frac{k}{8}$个链表等等
• 重复这个过程，直到不能再合并

代码实现

>folded main.go

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}

	return merge(lists)
}

func merge(lists []*ListNode) *ListNode {
	llen := len(lists)
	mid := llen / 2

	if llen == 1 {
		return lists[0]
	}

	if llen == 2 {
		l1, l2 := lists[0], lists[1]
		res, cur := &ListNode{}, &ListNode{}

		if l1 == nil {
			return l2
		}

		if l2 == nil {
			return l1
		}

		if l1.Val < l2.Val {
			res = l1
			cur.Next = l1
			l1 = l1.Next
		} else {
			res = l2
			cur.Next = l2
			l2 = l2.Next
		}
		cur = cur.Next
		
		for l1 != nil && l2 != nil {
			if l1.Val < l2.Val {
				cur.Next = l1
				l1 = l1.Next
			} else {
				cur.Next = l2
				l2 = l2.Next
			}
			cur = cur.Next
		}

		if l1 != nil {
			cur.Next = l1
		}

		if l2 != nil {
			cur.Next = l2
		}

		return res
	}

	return mergeKLists([]*ListNode{mergeKLists(lists[mid:]), mergeKLists(lists[:mid])})
}

三、思路二

优先队列

建立优先队列(大根堆或者小根堆均可)，每次让链表头元素入队，一轮比较后，如果该元素被弹出，对应的链表则后移，后面的元素再入队。

代码实现

>folded main.go

func mergeKLists2(lists []*ListNode) *ListNode {
	if lists == nil || len(lists) == 0 {
		return nil
	}

	// golang容器中的heap
	var h MinHeap
	heap.Init(&h)

	for _, l := range lists {
		if l != nil {
			heap.Push(&h, l)
		}
	}

	dummy := &ListNode{}
	p := dummy

	for h.Len() > 0 {
		min := heap.Pop(&h).(*ListNode)
		p.Next = min
		p = p.Next
		if min.Next != nil {
			heap.Push(&h, min.Next)
		}
	}
	return dummy.Next
}