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
Hiring now
Software engineer roles are open right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY
Next question