23. Merge k Sorted Lists
https://leetcode.com/problems/merge-k-sorted-lists/
Hard
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6
Example 2:
Input: lists = [] Output: []
Example 3:
Input: lists = [[]] Output: []
Constraints:
k == lists.length0 <= k <= 1040 <= lists[i].length <= 500-104 <= lists[i][j] <= 104lists[i]is sorted in ascending order.- The sum of
lists[i].lengthwill not exceed104.
題意
將 k 個已經排好順序的 linked list 合併成為一個排好序的 list。
解題思路
如果一個一個合併匯總成一個 list ，這樣暴力破解，相當的的沒效率，所以我們來換個思路來解這一題。
如果我一次合併兩個 list ，然後再將每兩個 list 得出的 list 再次合併呢？速度是不是快多了！
- 我們先將兩個 list 合併的方法撰寫出來。
- 我們來撰寫一個方法，每次合併會將低位與中位的 list 合併，並且還會將 中位 + 1 與高位的 list 合併。
- 然後在呼叫自己遞歸，重複上述得動作。
- 然後再將第二步與第三部得到的 list 合併起來，結果就出來了啦。
原始碼
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
return mergeLists(lists, 0, len(lists) - 1)
}
func mergeLists(lists []*ListNode, low, high int) *ListNode {
if low == high {
return lists[low]
}
if low > high {
return nil
}
mid := (low + high) / 2
return merge(mergeLists(lists, low, mid), mergeLists(lists, mid + 1, high))
}
func merge(list1, list2 *ListNode) *ListNode {
if list1 == nil {
return list2
}
if list2 == nil {
return list1
}
sentinel := &ListNode{}
last := sentinel
for list1 != nil && list2 != nil {
if list1.Val > list2.Val {
last.Next = list2
list2 = list2.Next
} else {
last.Next = list1
list1 = list1.Next
}
last = last.Next
}
if list1 != nil {
last.Next = list1
}
if list2 != nil {
last.Next = list2
}
return sentinel.Next
}
結尾
你有更好或更簡單的解決方案嗎？
歡迎到我的 Facebook Alan 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。
