Merge K sorted Lists
NetAppThe problem
Given heads of k sorted linked lists** **as an array called heads, merge them into one **single sorted **linked list and return the **head **of that list.
Input: heads = [[head -> 1 -> 2 -> 3 -> 4], [head -> -4 -> -3], [head -> -5 -> -3 -> 1 -> 2 -> 3 -> 4]] Output: head -> -5 -> -4 -> -3 -> -3 -> 1 -> 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4 Explanation: head -> -5 -> -4 -> -3 -> -3 -> 1 -> 1 -> 2 -> 2 ->** 3** -> 3 -> **4 **-> 4 The nodes in bold come from the 3rd list, the underlined nodes come from the 2nd list, rest are from the 1st list.
Input: heads = [[head -> -5 -> -4 -> -1], [head -> 10 -> 11 -> 12]] Output: head -> -5 -> -4 -> -1 -> 10 -> 11 -> 12 Explanation: head -> -5 -> -4 ->** -1** -> 10 -> 11 -> 12 The nodes in bold come from the 1st list, rest are from the 2nd list.
Input: heads = [[head -> 10 -> 12], [head -> 10 -> 12], [head -> 10 -> 10 -> 12]]
- 2 <= k <= 100
- 1 <= number of nodes in each list <= 100
- -1000 <= values of each node <= 1000
- All lists are sorted in non-decreasing order.
cpp
/*
Definition of singly linked list:
struct ListNode
{
int val;
ListNode *next;
ListNode(int data1)
{
val = data1;
next = NULL;
}
ListNode(int data1, ListNode *next1)
{
val = data1;
next = next1;
}
};
*/
class Solution {
public:
ListNode* mergeKSortedLists(vector<ListNode*> &head) {
}
};java
/*Definition for singly Linked List
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
*/
class Solution {
public ListNode mergeKSortedLists(List<ListNode> heads) {
}
}python
# Definiton of singly Linked List
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKSortedLists(self, heads):javascript
/*Definiton of singly Linked List
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
*/
class Solution {
mergeKSortedLists(heads) {
}
}csharp
/*
Definition of singly linked list:
public class ListNode
{
public int Val;
public ListNode Next;
public ListNode()
{
this.Val = 0;
this.Next = null;
}
public ListNode(int val)
{
this.Val = val;
this.Next = null;
}
public ListNode(int val, ListNode next)
{
this.Val = val;
this.Next = next;
}
}
*/
public class Solution {
public ListNode MergeKSortedLists(List<ListNode> heads) {
// Write your code here
return null;
}
}go
func mergeKSortedLists(heads []*ListNode) *ListNode {
}Stuck? Show a way to structure it+
- 01Push each non-null head into a min-heap
- 02Pop the smallest node and attach it to a dummy tail
- 03Push its next node if present
- 04Terminate the final tail and return dummy.next
Reference answer
Then expect these follow-ups
How does divide-and-conquer merging compare?
Tests: follow-up reasoning
What are the time and space costs?
Tests: complexity analysis
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question