23. 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.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 10^4.

解題

第一個方法:使用暴力解
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
nodes := make([]int, 0)
​
for _, list := range lists {
for list != nil {
nodes = append(nodes, list.Val)
list = list.Next
}
}
​
sort.Ints(nodes)
ans := &ListNode{}
head := ans
for _, n := range nodes {
ans.Next = &ListNode{ Val: n, Next: nil }
ans = ans.Next
}
​
return head.Next
}
Divide & Conquer
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 { return nil }
​
return helper(lists, 0, len(lists) - 1)
}
​
func helper(lists []*ListNode, start, end int) *ListNode {
if start > end { return nil }
if start == end { return lists[start] }
​
mid := start + (end-start)/2
left := helper(lists, start, mid);
right := helper(lists, mid + 1, end);
​
return merge(left, right)
}
​
func merge(head1 *ListNode, head2 *ListNode) *ListNode {
res := &ListNode{ Val:-1 }
tail := res
​
for head1 != nil && head2 != nil {
if head1.Val < head2.Val {
tail.Next = head1
head1 = head1.Next
} else {
tail.Next = head2
head2 = head2.Next
}
tail = tail.Next
}
​
if head1 != nil {
tail.Next = head1
}
if head2 != nil {
tail.Next = head2
}
​
return res.Next
}
​