Learn DSA
Depth-First Search
Greedy Algorithms
Heap
Merge K Sorted Lists
hard
Watch Video Walkthrough
Watch a video walking through the coding problem step-by-step
Watch Video Walkthrough
Watch a video walking through the coding problem step-by-step
DESCRIPTION (credit Leetcode.com)
Given k linked lists, each sorted in ascending order, in a list lists, write a function to merge the input lists into one sorted linked list.
Example 1:
Inputs:
Output:
-1 -> 2 -> 3 -> 3 -> 4 -> 5 -> 6 -> 6
💻 Desktop Required
The code editor works best on larger screens. Please open this page on your computer to write and run code.
"Write a function that takes a list of k sorted arrays `lists` and merges them into one sorted array and returns it."
Run your code to see results here
Have suggestions or found something wrong?
Explanation
Step 1: Initialize the heap
from heapq import heappush, heappopdef mergeKLists(lists):if not lists:return Noneheap = []for i, node in enumerate(lists):if node:heappush(heap, (node.val, i, node))dummy = ListNode(0)curr = dummywhile heap:val, idx, node = heappop(heap)curr.next = nodecurr = curr.nextif node.next:heappush(heap, (node.next.val, idx, node.next))return dummy.next
initialize heap
0 / 3
Step 2: Build the merged list
from heapq import heappush, heappopdef mergeKLists(lists):if not lists:return Noneheap = []for i, node in enumerate(lists):if node:heappush(heap, (node.val, i, node))dummy = ListNode(0)curr = dummywhile heap:val, idx, node = heappop(heap)curr.next = nodecurr = curr.nextif node.next:heappush(heap, (node.next.val, idx, node.next))return dummy.next
add -1 to heap
0 / 1
from heapq import heappush, heappopdef mergeKLists(lists):if not lists:return Noneheap = []for i, node in enumerate(lists):if node:heappush(heap, (node.val, i, node))dummy = ListNode(0)curr = dummywhile heap:val, idx, node = heappop(heap)curr.next = nodecurr = curr.nextif node.next:heappush(heap, (node.next.val, idx, node.next))return dummy.next
initialize dummy node
0 / 1
from heapq import heappush, heappopdef mergeKLists(lists):if not lists:return Noneheap = []for i, node in enumerate(lists):if node:heappush(heap, (node.val, i, node))dummy = ListNode(0)curr = dummywhile heap:val, idx, node = heappop(heap)curr.next = nodecurr = curr.nextif node.next:heappush(heap, (node.next.val, idx, node.next))return dummy.next
add -1 to result
0 / 1
from heapq import heappush, heappopdef mergeKLists(lists):if not lists:return Noneheap = []for i, node in enumerate(lists):if node:heappush(heap, (node.val, i, node))dummy = ListNode(0)curr = dummywhile heap:val, idx, node = heappop(heap)curr.next = nodecurr = curr.nextif node.next:heappush(heap, (node.next.val, idx, node.next))return dummy.next
0 / 1
Solution
from heapq import heappush, heappopdef mergeKLists(lists):if not lists:return Noneheap = []for i, node in enumerate(lists):if node:heappush(heap, (node.val, i, node))dummy = ListNode(0)curr = dummywhile heap:val, idx, node = heappop(heap)curr.next = nodecurr = curr.nextif node.next:heappush(heap, (node.next.val, idx, node.next))return dummy.next
merge k sorted lists
0 / 19
Complexity Analysis
Login to track your progress
Your account is free and you can post anonymously if you choose.