23. 合并 K 個升序鏈表

給你一個鏈表數組，每個鏈表都已經按升序排列。

請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

---

正文

這道題有多種解決方案

堆

比較容易，又比較直觀的就是堆排序，將每個節點加入最小根堆中，依次彈出加入最后的鏈表，就可得出答案，事實上，并不需要每次都將所有鏈表加入，只需要最開始將每個鏈表的頭節點加入，然后在彈出鏈表時，直接將彈出的節點的下一個節點再加入堆即可，這樣能夠有效節省空間。

代碼如下：

func mergeKLists(lists []*ListNode) *ListNode {lh := &ListHeap{}heap.Init(lh)for _, node := range lists {if node != nil {heap.Push(lh, node)}}dummy := &ListNode{}tmp := dummyfor lh.Len() > 0 {Node := heap.Pop(lh).(*ListNode)tmp.Next = Nodetmp = tmp.Nextif Node.Next != nil {heap.Push(lh, Node.Next)}}return dummy.Next
}type ListHeap []*ListNodefunc (l *ListHeap) Len() int {return len(*l)
}func (l *ListHeap) Less(i, j int) bool {return (*l)[i].Val < (*l)[j].Val
}func (l *ListHeap) Swap(i, j int) {(*l)[i], (*l)[j] = (*l)[j], (*l)[i]
}func (l *ListHeap) Push(x any) {*l = append(*l, x.(*ListNode))
}func (l *ListHeap) Pop() any {res := (*l)[len(*l)-1]*l = (*l)[:len(*l)-1]return res
}

堆排序不用ide也太難寫了~

分治

跟歸并排序的思路類似，將鏈表切片分成兩部分，分別合并成一個鏈表，再將這兩個鏈表進行合并。

可以理解為：

	鏈表1  鏈表2    鏈表3    鏈表4|		  |		|		  ||		  |		|		  ||		  |		|		  ||		  |		|		  |+————+————+     +————+————+|			 	 |鏈表			鏈表+————————+——————+||最終鏈表

代碼如下：

func mergeKLists(lists []*ListNode) *ListNode {return Merge(lists, 0, len(lists) - 1)
}func Merge(lists []*ListNode, l int, r int) *ListNode {if l == r {return lists[l]} else if l > r {return nil}mid := (l + r) / 2return MergeTwoLists(Merge(lists, l, mid), Merge(lists, mid + 1, r))
}func MergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {dummy := &ListNode{}tmp := dummyfor list1 != nil && list2 != nil {if list1.Val > list2.Val {tmp.Next = list2tmp = tmp.Nextlist2 = list2.Next} else {tmp.Next = list1tmp = tmp.Nextlist1 = list1.Next}}if list1 != nil {tmp.Next = list1}if list2 != nil {tmp.Next = list2}return dummy.Next
}

---