0023. Merge k Sorted Lists
Hard | Linked List + Sort | 76 ms (98.81%), 22.3 MB (39.22%)
Source: LeetCode - Merge k Sorted Lists GitHub: Solution / Performance
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.
Constraints:
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]is sorted in ascending order.The sum of
lists[i].lengthwon't exceed10^4.
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
Input: lists = []
Output: []
Input: lists = [[]]
Output: []We could use the "Merge with Divide and Conquer" method for better performance. Generally speaking, we do merge starting with 2 lists per iteration, then increasing to 4 lists per iteration, etc.
# size = 1, len = 5
# for i in range(0, len - size, size * 2)
# i = 0, 2, 4
# merge input = [0, 1] [2, 3] [4, 5]
['l0', l1, 'l2', l3, 'l4']
| / | / |
| / | / |
|/ |/ |
l0 l2 l4
# size = 2, len = 5
# for i in range(0, len - size, size * 2)
# i = 0
# merge input = [0, 2]
['l0', l1, l2, l3, l4]
| / |
|-------* |
l0 l4
# size = 4, len = 5
# for i in range(0, len - size, size * 2)
# i = 0
# merge input = [0, 4]
['l0', l1, l2, l3, l4]
| /
|---------------*
l0class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# (base case)
if len(lists) == 0: return None
if len(lists) == 1: return lists[0]
# ==================================================
# Linked List + Sort =
# ==================================================
# time : O(nlogk)
# space : O(1)
#
# n is the total number of nodes in two linked lists
# k is the number of linked lists
size = 1
while size < len(lists):
for i in range(0, len(lists) - size, size * 2):
lists[i] = self.merge2Lists(lists[i], lists[i+size])
size *= 2
return lists[0]
def merge2Lists(self, l1: ListNode, l2: ListNode) -> ListNode:
ret = ListNode(0)
cur = ret
while l1 and l2:
if l1.val < l2.val:
cur.next = ListNode(l1.val)
cur = cur.next
l1 = l1.next
else:
cur.next = ListNode(l2.val)
cur = cur.next
l2 = l2.next
cur.next = l1 or l2
return ret.next
class Solution {
/**
* @time : O(nlogk)
* @space : O(1)
*/
public ListNode mergeKLists(ListNode[] lists) {
/* base case */
if(lists.length == 0) return null;
if(lists.length == 1) return lists[0];
int size = 1;
while(size < lists.length) {
for(int i=0 ; i<lists.length-size ; i+=size*2) {
lists[i] = merge2Lists(lists[i], lists[i+size]);
}
size *= 2;
}
return lists[0];
}
public ListNode merge2Lists(ListNode l1, ListNode l2) {
ListNode ret = new ListNode(0);
ListNode cur = ret;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
cur.next = new ListNode(l1.val);
l1 = l1.next;
} else {
cur.next = new ListNode(l2.val);
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l2 == null) ? l1 : l2;
return ret.next;
}
}
Last updated
Was this helpful?