Leetcode.23 合并K个升序链表

Leetcode.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

解法：
利用小根堆思路，把每个链表的头结点按照小根堆排列，pop 出来的节点取下来放到结果链表上，然后再将新的头结点 push 进去，重复此过程即可得到所求

impost (
	"container/heap"
)
/** * Definition for singly-linked list. * 
type ListNode struct { 
	* Val int 
	* Next *ListNode 
} */ 

func mergeKLists(lists []*ListNode) *ListNode { 
	pq := hp{} 
	for _, head := range lists { 
		if head != nil { 
			pq = append(pq, head) 
		} 
	} 
	
	heap.Init(&pq) 
	dummy := &ListNode{} 
	cur := dummy 
	for len(pq) > 0 { 
		cur.Next = heap.Pop(&pq).(*ListNode) 
		cur = cur.Next 
		if cur.Next != nil { 
			heap.Push(&pq, cur.Next) 
		} 
	} 
	return dummy.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 any) { 
	*h = append(*h, v.(*ListNode)) 
} 
func (h *hp) Pop() any { 
	a := *h
	v := a[len(a)-1]
	*h = a[:len(a)-1]
	return v 
} 

左右分治 + 合并两个有序链表

/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	n := len(lists)
	left := mergeKLists(lists[:n/2])
	right := mergeKLists(lists[n/2:])
	return merge2Lists(left, right)
}
  
func merge2Lists(h1, h2 *ListNode) *ListNode {
	dummy := &ListNode{}
	t, t1, t2 := dummy, h1, h2
	for t1 != nil && t2 != nil {
		if t1.Val <= t2.Val {
			t.Next = t1
			t1 = t1.Next
		} else {
			t.Next = t2
			t2 = t2.Next
		}
		t = t.Next
	}
	  
	if t1 != nil {
		t.Next = t1
	} else if t2 != nil {
		t.Next = t2
	}
	return dummy.Next
}