Merge Linked Lists
HardPremium
Merge K Sorted Linked Lists. You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Your task is to merge all the linked-lists into one sorted linked-list and return it.
Examples:
- If
lists = [[1,4,5],[1,3,4],[2,6]], where each array represents a linked-list, the merged and sorted linked-list would be[1,1,2,3,4,4,5,6]. The output for the merged list should be in array form for simplicity. - If
lists = [], indicating an array of no linked-lists, the output should be[]. - If
lists = [[]], representing an array with a single empty linked-list, the output should be[]. - If
lists = [[],[1]], where the first linked-list is empty and the second contains a single element, the output should be[1]. - If
lists = [[-1,5,11],[],[6,10]], the merged and sorted linked-list should be[-1,5,6,10,11].
Constraints:
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 50010^4 <= lists[i][j] <= 10^4lists[i]is sorted in an increasing order.
import queue
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __eq__(self, other):
return self.val == other.val
def __lt__(self, other):
return self.val < other.val
def mergeKLists(lists):
if len(lists) == 0:
return None
pq = queue.PriorityQueue()
for listHead in lists:
if listHead is not None:
entry = (listHead.val, listHead)
pq.put(entry)
newHead = None
currNode = None
while not pq.empty():
nodeValue, node = pq.get() # Gives us the minimum value node
nextNode = node.next
if nextNode is not None:
entry = (nextNode.val, nextNode)
pq.put(entry)
if newHead is None:
newHead = node
currNode = node
else:
currNode.next = node
currNode = node
return newHeadIn this video, Simon, Spotify Software Engineer, answers an interview question about merging k sorted linked lists.
A much better solution than the one in the article, below: It looks like the ones writing articles here in Javascript do not understand the time/space complexity of javascript methods. shift, splice, sort, etc... In the solution article you have a shift and a sort being done inside a while, that is, the multiplication of Ns. My solution, below, iterates through the list once and then sorts it, separately. It´s O(N+Log(N))
class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } } // N is total number of nodes from all the lists // 1 - Does One Iteration through all Nodes // 2 - Does one Sorting on all nodes // O(N+Log(N)) function mergeKLists(lists) { const listLength = lists.length; if (!listLength) return; const unorderedList = [] let i = 0; let currentLoopHead = lists[i] // In case of inputs like [[],[1]] while (!currentLoopHead && i < listLength) { currentLoopHead = lists[i++] } while (currentLoopHead) { unorderedList.push([currentLoopHead.val, currentLoopHead]) if (currentLoopHead.next) { currentLoopHead = currentLoopHead.next } else { currentLoopHead = lists[++i] } } let orderedList = unorderedList.sort((pairA, pairB) => { if (pairA[0] > pairB[0]) { pairB[1].next = pairA[1] return 1 } if (pairA[0] < pairB[0]) { pairA[1].next = pairB[1] return -1 } pairA[1].next = pairB[1] return 0 }) return orderedList[0][1] } // debug your code below let list1 = new ListNode(1, new ListNode(4, new ListNode(5))); let list2 = new ListNode(1, new ListNode(3, new ListNode(4))); let list3 = new ListNode(2, new ListNode(6)); let lists = [list1, list2, list3]; let merged = mergeKLists(lists); console.log("Merged list:"); while (merged) { process.stdout.write(merged.val.toString()); if (merged.next) { process.stdout.write(" -> "); } else { console.log(); } merged = merged.next; }