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.
Problem
Merge k already-sorted linked lists into one sorted list.
Approach
Brute-force merging one by one would be very inefficient. Instead, we merge two lists at a time and recursively combine the results — divide and conquer!
- Write a method to merge two lists.
- Write a method that merges the low-to-mid range and the (mid+1)-to-high range.
- Recursively call itself, repeating the process.
- Merge the results — and we have our answer!
Source Code
/**
* 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
}
Closing
Do you have a better or simpler solution?
Feel free to leave a comment on my blog. Your feedback motivates me to keep writing. Thank you for reading, and let’s grow together to become better versions of ourselves.
