Flattening of LL
Linked-List
FAQs (Hard)
Hard
- One of the real-world applications of this problem is seen in the representation and manipulation of complex hierarchical structures, such as the Document Object Model (DOM) in web development
- The DOM is essentially a tree-like structure where each HTML element is a node with potential child and sibling nodes
- The concept of flattening a nested structure is commonly used in DOM manipulation for a variety of reasons, including improving the performance of traversing the structure or simplifying the complexity when applying certain operations
- The same principle can be applied to linked lists structures that are used for storing and organizing data in sophisticated applications
Given a special linked list containing n head nodes where every node in the linked list contains two pointers:
- âNextâ points to the next node in the list
- âChildâ pointer to a linked list where the current node is the head
Each of these child linked lists is in sorted order and connected by a 'child' pointer.
Flatten this linked list such that all nodes appear in a single sorted layer connected by the 'child' pointer and return the head of the modified list.
Constraints
- n == Number of head nodes
- 1 <= n <= 100
- 1 <= Number of nodes in each child linked list <= 100
- 0 <= ListNode.val <= 1000
- All child linked lists are sorted in non-decreasing order
Hints
- A brute-force approach would: Extract all nodes into an array (O(n) space). Sort the array (O(N log N) time). Reconstruct the list using the child pointer.
- Since each child list is already sorted, we can efficiently merge them using: Priority Queue / Min-Heap (O(N log k)) Iterative Merging (Similar to Merge k Sorted Lists in Linked Lists) (O(N log k)) Divide and Conquer (Merging Pairs of Lists Efficiently) (O(N log k))
Company Tags
GE Healthcare
Western Digital
Riot Games
Alibaba
Optum
Unity Technologies
Bloomberg
KPMG
PwC
Morgan Stanley
HCL Technologies
DoorDash
Siemens Healthineers
IBM
Airbnb
Robinhood
Walmart
Docker
Broadcom
Intel
Roche
Goldman Sachs
Rockstar Games
Zoho
Snowflake
Google
Microsoft
Amazon
Meta
Apple
Netflix
Adobe
Editorial
Intuition
The given linked list can be transformed into a single level sorted list by initializing an array to temporarily store nodes during traversal. Traverse the list, first following the top-level next pointers, then accessing each node's child pointers, adding all nodes to the array.
Sort the array to arrange the values sequentially, then create and return a new linked list from the sorted array.
Approach
- Initialize an array to store node values and traverse the list, collecting values from both top-level and child nodes.
- Sort the array to arrange the values in ascending order.
- Create and return a new linked list from the sorted array.
Dry Run
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142
#include <bits/stdc++.h>
using namespace std;
// Definition of special linked list:
struct ListNode {
int val;
ListNode *next;
ListNode *child;
ListNode() {
val = 0;
next = NULL;
child = NULL;
}
ListNode(int data1) {
val = data1;
next = NULL;
child = NULL;
}
ListNode(int data1, ListNode *next1, ListNode* next2) {
val = data1;
next = next1;
child = next1;
}
};
class Solution {
private:
// Function to convert a vector to a linked list
ListNode* convertArrToLinkedList(vector<int>& arr) {
/* Create a dummy node to serve as
the head of the linked list */
ListNode* dummyNode = new ListNode(-1);
ListNode* temp = dummyNode;
/* Iterate through the vector and
create nodes with vector elements */
for (int i=0; i < arr.size(); i++) {
// Create a new node with the vector element
temp->child = new ListNode(arr[i]);
// Update the temporary pointer
temp = temp->child;
}
/* Return the linked list starting
from the next of the dummy node */
return dummyNode->child;
}
public:
// Function to flatten a linked list with child pointers
ListNode* flattenLinkedList(ListNode* head) {
vector<int> arr;
// Traverse through the linked list
while (head != nullptr) {
/* Traverse through the child
nodes of each head node */
ListNode* t2 = head;
while (t2 != nullptr) {
// Store each node's data in the array
arr.push_back(t2->val);
// Move to the next child node
t2 = t2->child;
}
// Move to the next head node
head = head->next;
}
// Sort the array containing node values
sort(arr.begin(), arr.end());
// Convert the sorted array back to a linked list
return convertArrToLinkedList(arr);
}
};
// Function to print the linked list
void printLinkedList(ListNode* head) {
while (head != nullptr) {
cout << head->val << " ";
head = head->child;
}
cout << endl;
}
// Function to print the linked list in a grid-like structure
void printOriginalLinkedList(ListNode* head, int depth) {
while (head != nullptr) {
cout << head->val;
/* If child exists, recursively
print it with indentation */
if (head->child) {
cout << " -> ";
printOriginalLinkedList(head->child, depth + 1);
}
// Add vertical bars for each level in the grid
if (head->next) {
cout << endl;
for (int i = 0; i < depth; ++i) {
cout << "| ";
}
}
head = head->next;
}
}
int main() {
// Create a linked list with child pointers
ListNode* head = new ListNode(5);
head->child = new ListNode(14);
head->next = new ListNode(10);
head->next->child = new ListNode(4);
head->next->next = new ListNode(12);
head->next->next->child = new ListNode(20);
head->next->next->child->child = new ListNode(13);
head->next->next->next = new ListNode(7);
head->next->next->next->child = new ListNode(17);
// Print the original linked list structure
cout << "Original linked list:" << endl;
printOriginalLinkedList(head, 0);
// Creating an instance of Solution class
Solution sol;
// Function call to flatten the linked list
ListNode* flattened = sol.flattenLinkedList(head);
// Printing the flattened linked list
cout << "\nFlattened linked list: ";
printLinkedList(flattened);
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141
import java.util.*;
class ListNode {
int val;
ListNode next;
ListNode child;
ListNode() {
val = 0;
next = null;
child = null;
}
ListNode(int data1) {
val = data1;
next = null;
child = null;
}
ListNode(int data1, ListNode next1, ListNode next2) {
val = data1;
next = next1;
child = next1;
}
}
class Solution {
// Function to convert a vector to a linked list
private ListNode convertArrToLinkedList(List<Integer> arr) {
/* Create a dummy node to serve as
the head of the linked list */
ListNode dummyNode = new ListNode(-1);
ListNode temp = dummyNode;
/* Iterate through the vector and
create nodes with vector elements */
for (int i = 0; i < arr.size(); i++) {
// Create a new node with the vector element
temp.child = new ListNode(arr.get(i));
// Update the temporary pointer
temp = temp.child;
}
/* Return the linked list starting
from the next of the dummy node */
return dummyNode.child;
}
// Function to flatten a linked list with child pointers
public ListNode flattenLinkedList(ListNode head) {
List<Integer> arr = new ArrayList<>();
// Traverse through the linked list
while (head != null) {
/* Traverse through the child
nodes of each head node */
ListNode t2 = head;
while (t2 != null) {
// Store each node's data in the array
arr.add(t2.val);
// Move to the next child node
t2 = t2.child;
}
// Move to the next head node
head = head.next;
}
// Sort the array containing node values
Collections.sort(arr);
// Convert the sorted array back to a linked list
return convertArrToLinkedList(arr);
}
}
// Function to print the linked list
class Main {
public static void printLinkedList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.child;
}
System.out.println();
}
// Function to print the linked list in a grid-like structure
public static void printOriginalLinkedList(ListNode head, int depth) {
while (head != null) {
System.out.print(head.val);
/* If child exists, recursively
print it with indentation */
if (head.child != null) {
System.out.print(" -> ");
printOriginalLinkedList(head.child, depth + 1);
}
// Add vertical bars for each level in the grid
if (head.next != null) {
System.out.println();
for (int i = 0; i < depth; ++i) {
System.out.print("| ");
}
}
head = head.next;
}
}
public static void main(String[] args) {
// Create a linked list with child pointers
ListNode head = new ListNode(5);
head.child = new ListNode(14);
head.next = new ListNode(10);
head.next.child = new ListNode(4);
head.next.next = new ListNode(12);
head.next.next.child = new ListNode(20);
head.next.next.child.child = new ListNode(13);
head.next.next.next = new ListNode(7);
head.next.next.next.child = new ListNode(17);
// Print the original linked list structure
System.out.println("Original linked list:");
printOriginalLinkedList(head, 0);
// Creating an instance of Solution class
Solution sol = new Solution();
// Function call to flatten the linked list
ListNode flattened = sol.flattenLinkedList(head);
// Printing the flattened linked list
System.out.print("\nFlattened linked list: ");
printLinkedList(flattened);
}
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
class ListNode:
def __init__(self, val=0, next=None, child=None):
self.val = val
self.next = next
self.child = child
class Solution:
# Function to convert a vector to a linked list
def convertArrToLinkedList(self, arr):
''' Create a dummy node to serve as
the head of the linked list '''
dummyNode = ListNode(-1)
temp = dummyNode
''' Iterate through the vector and
create nodes with vector elements '''
for i in range(len(arr)):
# Create a new node with the vector element
temp.child = ListNode(arr[i])
# Update the temporary pointer
temp = temp.child
''' Return the linked list starting
from the next of the dummy node '''
return dummyNode.child
# Function to flatten a linked list with child pointers
def flattenLinkedList(self, head):
arr = []
# Traverse through the linked list
while head is not None:
''' Traverse through the child
nodes of each head node '''
t2 = head
while t2 is not None:
# Store each node's data in the array
arr.append(t2.val)
# Move to the next child node
t2 = t2.child
# Move to the next head node
head = head.next
# Sort the array containing node values
arr.sort()
# Convert the sorted array back to a linked list
return self.convertArrToLinkedList(arr)
# Function to print the linked list
def printLinkedList(head):
while head is not None:
print(head.val, end=" ")
head = head.child
print()
# Function to print the linked list in a grid-like structure
def printOriginalLinkedList(head, depth):
while head is not None:
print(head.val, end="")
''' If child exists, recursively
print it with indentation '''
if head.child:
print(" -> ", end="")
printOriginalLinkedList(head.child, depth + 1)
# Add vertical bars for each level in the grid
if head.next:
print()
for i in range(depth):
print("| ", end="")
head = head.next
if __name__ == "__main__":
# Create a linked list with child pointers
head = ListNode(5)
head.child = ListNode(14)
head.next = ListNode(10)
head.next.child = ListNode(4)
head.next.next = ListNode(12)
head.next.next.child = ListNode(20)
head.next.next.child.child = ListNode(13)
head.next.next.next = ListNode(7)
head.next.next.next.child = ListNode(17)
# Print the original linked list structure
print("Original linked list:")
printOriginalLinkedList(head, 0)
# Creating an instance of Solution class
sol = Solution()
# Function call to flatten the linked list
flattened = sol.flattenLinkedList(head)
# Printing the flattened linked list
print("\nFlattened linked list: ", end="")
printLinkedList(flattened)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119
class ListNode {
constructor(val = 0, next = null, child = null) {
this.val = val;
this.next = next;
this.child = child;
}
}
class Solution {
// Function to convert an array to a linked list
convertArrToLinkedList(arr) {
/* Create a dummy node to serve as
the head of the linked list */
let dummyNode = new ListNode(-1);
let temp = dummyNode;
/* Iterate through the array and
create nodes with array elements */
for (let i = 0; i < arr.length; i++) {
// Create a new node with the array element
temp.child = new ListNode(arr[i]);
// Update the temporary pointer
temp = temp.child;
}
/* Return the linked list starting
from the next of the dummy node */
return dummyNode.child;
}
// Function to flatten a linked list with child pointers
flattenLinkedList(head) {
let arr = [];
// Traverse through the linked list
while (head !== null) {
/* Traverse through the child
nodes of each head node */
let t2 = head;
while (t2 !== null) {
// Store each node's data in the array
arr.push(t2.val);
// Move to the next child node
t2 = t2.child;
}
// Move to the next head node
head = head.next;
}
// Sort the array containing node values
arr.sort((a, b) => a - b);
// Convert the sorted array back to a linked list
return this.convertArrToLinkedList(arr);
}
}
// Function to print the linked list
function printLinkedList(head) {
while (head !== null) {
process.stdout.write(head.val + " ");
head = head.child;
}
console.log();
}
// Function to print the linked list in a grid-like structure
function printOriginalLinkedList(head, depth) {
while (head !== null) {
process.stdout.write(head.val.toString());
/* If child exists, recursively
print it with indentation */
if (head.child) {
process.stdout.write(" -> ");
printOriginalLinkedList(head.child, depth + 1);
}
// Add vertical bars for each level in the grid
if (head.next) {
console.log();
for (let i = 0; i < depth; ++i) {
process.stdout.write("| ");
}
}
head = head.next;
}
}
let head = new ListNode(5);
head.child = new ListNode(14);
head.next = new ListNode(10);
head.next.child = new ListNode(4);
head.next.next = new ListNode(12);
head.next.next.child = new ListNode(20);
head.next.next.child.child = new ListNode(13);
head.next.next.next = new ListNode(7);
head.next.next.next.child = new ListNode(17);
// Print the original linked list structure
console.log("Original linked list:");
printOriginalLinkedList(head, 0);
// Creating an instance of Solution class
let sol = new Solution();
// Function call to flatten the linked list
let flattened = sol.flattenLinkedList(head);
// Printing the flattened linked list
console.log("\nFlattened linked list: ");
printLinkedList(flattened);Complexity Analysis
Time Complexity: O(NxM) + O(NxM log(NxM)) + O(NxM) where N is the number of nodes along the next pointers and M is the number of nodes along the child pointers.
- O(NxM) because we traverse through all the nodes, iterating through N nodes along the next pointers and M nodes along the child pointers.
- O(NxM log(NxM)) because we sort the array containing NxM total elements.
- O(NxM) because we reconstruct the linked list from the sorted array by iterating over the NxM elements.
Space Complexity: O(NxM) + O(NxM) where N is the number of nodes along the next pointers and M is the number of nodes along the child pointers.
- O(NxM) for storing all the elements in an additional array for sorting.
- O(NxM) to reconstruct the linked list from the array after sorting.
Intuition
The optimized approach is based on the fact that the child linked lists are already sorted. By merging these pre-sorted lists directly during traversal, we can eliminate the additional space and time complexity generated by sorting.
Instead of collecting all node values into an array and then sorting them, we can merge these sorted vertical linked lists efficiently in place. This eliminates the need for additional sorting steps and avoids allocating extra space for the combined linked list.
The base case ensures the termination of the recursion when there's either no list or only a single node remaining. The recursive function then handles the merging of the remaining lists after recursive flattening, creating a sorted flattened linked list.
Approach
-
Establish base case conditions by checking if the head is null or has no next pointer. If either condition is met, return the head, as there is no further flattening or merging required.
-
Recursively initiate the flattening process by calling
flattenLinkedListon the next node (head -> next). The result of this recursive call will be the head of the flattened and merged linked list. -
Within the recursive call, perform merge operations by calling a merge function. This function merges the current list with the already flattened and merged list based on their data values. The merged list is then updated in the head and returned as the result of the flattening process.
Dry Run
Establishing of the base case
Using recursion to flatten the list
Solution
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145
#include <bits/stdc++.h>
using namespace std;
// Definition of special linked list
struct ListNode {
int val;
ListNode *next;
ListNode *child;
ListNode() {
val = 0;
next = NULL;
child = NULL;
}
ListNode(int data1) {
val = data1;
next = NULL;
child = NULL;
}
ListNode(int data1, ListNode *next1, ListNode* next2) {
val = data1;
next = next1;
child = next1;
}
};
class Solution {
private:
/* Merge the two linked lists in a particular
order based on the data value */
ListNode* merge(ListNode* list1, ListNode* list2){
/* Create a dummy node as a
placeholder for the result */
ListNode* dummyNode = new ListNode(-1);
ListNode* res = dummyNode;
// Merge the lists based on data values
while(list1 != NULL && list2 != NULL){
if(list1->val < list2->val){
res->child = list1;
res = list1;
list1 = list1->child;
}
else{
res->child = list2;
res = list2;
list2 = list2->child;
}
res->next = NULL;
}
// Connect the remaining elements if any
if(list1){
res->child = list1;
} else {
res->child = list2;
}
// Break the last node's link to prevent cycles
if(dummyNode->child){
dummyNode->child->next = NULL;
}
return dummyNode->child;
}
public:
// Function to flatten a linked list with child pointers
ListNode* flattenLinkedList(ListNode* head) {
// If head is null or there is no next node
if(head == NULL || head->next == NULL){
return head; // Return head
}
// Recursively flatten the rest of the linked list
ListNode* mergedHead = flattenLinkedList(head->next);
// Merge the lists
head = merge(head, mergedHead);
return head;
}
};
// Function to print the linked list
void printLinkedList(ListNode* head) {
while (head != nullptr) {
cout << head->val << " ";
head = head->child;
}
cout << endl;
}
// Function to print the linked list in a grid-like structure
void printOriginalLinkedList(ListNode* head, int depth) {
while (head != nullptr) {
cout << head->val;
/* If child exists, recursively
print it with indentation */
if (head->child) {
cout << " -> ";
printOriginalLinkedList(head->child, depth + 1);
}
// Add vertical bars for each level in the grid
if (head->next) {
cout << endl;
for (int i = 0; i < depth; ++i) {
cout << "| ";
}
}
head = head->next;
}
}
int main() {
// Create a linked list with child pointers
ListNode* head = new ListNode(5);
head->child = new ListNode(14);
head->next = new ListNode(10);
head->next->child = new ListNode(4);
head->next->next = new ListNode(12);
head->next->next->child = new ListNode(20);
head->next->next->child->child = new ListNode(13);
head->next->next->next = new ListNode(7);
head->next->next->next->child = new ListNode(17);
// Print the original linked list structure
cout << "Original linked list:" << endl;
printOriginalLinkedList(head, 0);
// Creating an instance of Solution class
Solution sol;
// Function call to flatten the linked list
ListNode* flattened = sol.flattenLinkedList(head);
// Printing the flattened linked list
cout << "\nFlattened linked list: ";
printLinkedList(flattened);
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144
import java.util.*;
// Definition of special linked list
class ListNode {
int val;
ListNode next;
ListNode child;
ListNode() {
val = 0;
next = null;
child = null;
}
ListNode(int data1) {
val = data1;
next = null;
child = null;
}
ListNode(int data1, ListNode next1, ListNode next2) {
val = data1;
next = next1;
child = next1;
}
}
class Solution {
/* Merge the two linked lists in a particular
order based on the data value */
private ListNode merge(ListNode list1, ListNode list2) {
/* Create a dummy node as a
placeholder for the result */
ListNode dummyNode = new ListNode(-1);
ListNode res = dummyNode;
// Merge the lists based on data values
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
res.child = list1;
res = list1;
list1 = list1.child;
} else {
res.child = list2;
res = list2;
list2 = list2.child;
}
res.next = null;
}
// Connect the remaining elements if any
if (list1 != null) {
res.child = list1;
} else {
res.child = list2;
}
// Break the last node's link to prevent cycles
if (dummyNode.child != null) {
dummyNode.child.next = null;
}
return dummyNode.child;
}
// Function to flatten a linked list with child pointers
public ListNode flattenLinkedList(ListNode head) {
// If head is null or there is no next node
if (head == null || head.next == null) {
return head; // Return head
}
// Recursively flatten the rest of the linked list
ListNode mergedHead = flattenLinkedList(head.next);
// Merge the lists
head = merge(head, mergedHead);
return head;
}
}
// Function to print the linked list
public class Main {
public static void printLinkedList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.child;
}
System.out.println();
}
// Function to print the linked list in a grid-like structure
public static void printOriginalLinkedList(ListNode head, int depth) {
while (head != null) {
System.out.print(head.val);
/* If child exists, recursively
print it with indentation */
if (head.child != null) {
System.out.print(" -> ");
printOriginalLinkedList(head.child, depth + 1);
}
// Add vertical bars for each level in the grid
if (head.next != null) {
System.out.println();
for (int i = 0; i < depth; ++i) {
System.out.print("| ");
}
}
head = head.next;
}
}
public static void main(String[] args) {
// Create a linked list with child pointers
ListNode head = new ListNode(5);
head.child = new ListNode(14);
head.next = new ListNode(10);
head.next.child = new ListNode(4);
head.next.next = new ListNode(12);
head.next.next.child = new ListNode(20);
head.next.next.child.child = new ListNode(13);
head.next.next.next = new ListNode(7);
head.next.next.next.child = new ListNode(17);
// Print the original linked list structure
System.out.println("Original linked list:");
printOriginalLinkedList(head, 0);
// Creating an instance of Solution class
Solution sol = new Solution();
// Function call to flatten the linked list
ListNode flattened = sol.flattenLinkedList(head);
// Printing the flattened linked list
System.out.print("\nFlattened linked list: ");
printLinkedList(flattened);
}
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106
class ListNode:
def __init__(self, val=0, next=None, child=None):
self.val = val
self.next = next
self.child = child
class Solution:
''' Merge the two linked lists in a particular
order based on the data value '''
def merge(self, list1, list2):
''' Create a dummy node as a
placeholder for the result '''
dummyNode = ListNode(-1)
res = dummyNode
# Merge the lists based on data values
while list1 is not None and list2 is not None:
if list1.val < list2.val:
res.child = list1
res = list1
list1 = list1.child
else:
res.child = list2
res = list2
list2 = list2.child
res.next = None
# Connect the remaining elements if any
if list1:
res.child = list1
else:
res.child = list2
# Break the last node's link to prevent cycles
if dummyNode.child:
dummyNode.child.next = None
return dummyNode.child
# Function to flatten a linked list with child pointers
def flattenLinkedList(self, head):
# If head is null or there is no next node
if head is None or head.next is None:
return head # Return head
# Recursively flatten the rest of the linked list
mergedHead = self.flattenLinkedList(head.next)
# Merge the lists
head = self.merge(head, mergedHead)
return head
# Function to print the linked list
def printLinkedList(head):
while head is not None:
print(head.val, end=" ")
head = head.child
print()
# Function to print the linked list in a grid-like structure
def printOriginalLinkedList(head, depth):
while head is not None:
print(head.val, end="")
''' If child exists, recursively
print it with indentation '''
if head.child:
print(" -> ", end="")
printOriginalLinkedList(head.child, depth + 1)
# Add vertical bars for each level in the grid
if head.next:
print()
for i in range(depth):
print("| ", end="")
head = head.next
if __name__ == "__main__":
# Create a linked list with child pointers
head = ListNode(5)
head.child = ListNode(14)
head.next = ListNode(10)
head.next.child = ListNode(4)
head.next.next = ListNode(12)
head.next.next.child = ListNode(20)
head.next.next.child.child = ListNode(13)
head.next.next.next = ListNode(7)
head.next.next.next.child = ListNode(17)
# Print the original linked list structure
print("Original linked list:")
printOriginalLinkedList(head, 0)
# Creating an instance of Solution class
sol = Solution()
# Function call to flatten the linked list
flattened = sol.flattenLinkedList(head)
# Printing the flattened linked list
print("\nFlattened linked list: ", end="")
printLinkedList(flattened)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120
class ListNode {
constructor(val = 0, next = null, child = null) {
this.val = val;
this.next = next;
this.child = child;
}
}
class Solution {
/* Merge the two linked lists in a particular
order based on the data value */
merge(list1, list2) {
/* Create a dummy node as a
placeholder for the result */
let dummyNode = new ListNode(-1);
let res = dummyNode;
// Merge the lists based on data values
while (list1 !== null && list2 !== null) {
if (list1.val < list2.val) {
res.child = list1;
res = list1;
list1 = list1.child;
} else {
res.child = list2;
res = list2;
list2 = list2.child;
}
res.next = null;
}
// Connect the remaining elements if any
if (list1 !== null) {
res.child = list1;
} else {
res.child = list2;
}
// Break the last node's link to prevent cycles
if (dummyNode.child !== null) {
dummyNode.child.next = null;
}
return dummyNode.child;
}
// Function to flatten a linked list with child pointers
flattenLinkedList(head) {
// If head is null or there is no next node
if (head === null || head.next === null) {
return head; // Return head
}
// Recursively flatten the rest of the linked list
let mergedHead = this.flattenLinkedList(head.next);
// Merge the lists
head = this.merge(head, mergedHead);
return head;
}
}
// Function to print the linked list
function printLinkedList(head) {
while (head !== null) {
process.stdout.write(head.val + " ");
head = head.child;
}
console.log();
}
// Function to print the linked list in a grid-like structure
function printOriginalLinkedList(head, depth) {
while (head !== null) {
process.stdout.write(head.val.toString());
/* If child exists, recursively
print it with indentation */
if (head.child) {
process.stdout.write(" -> ");
printOriginalLinkedList(head.child, depth + 1);
}
// Add vertical bars for each level in the grid
if (head.next) {
console.log();
for (let i = 0; i < depth; ++i) {
process.stdout.write("| ");
}
}
head = head.next;
}
}
let head = new ListNode(5);
head.child = new ListNode(14);
head.next = new ListNode(10);
head.next.child = new ListNode(4);
head.next.next = new ListNode(12);
head.next.next.child = new ListNode(20);
head.next.next.child.child = new ListNode(13);
head.next.next.next = new ListNode(7);
head.next.next.next.child = new ListNode(17);
// Print the original linked list structure
console.log("Original linked list:");
printOriginalLinkedList(head, 0);
// Creating an instance of Solution class
let sol = new Solution();
// Function call to flatten the linked list
let flattened = sol.flattenLinkedList(head);
// Printing the flattened linked list
console.log("\nFlattened linked list: ");
printLinkedList(flattened);Complexity Analysis
Time Complexity: O(Nx(2M)) ~ O(2NxM) where N is the length of the linked list along the next pointer and M is the length of the linked list along the child pointers.
- The merge operation in each recursive call takes time complexity proportional to the length of the linked lists being merged as they have to iterate over the entire lists. Since the vertical depth of the linked lists is assumed to be M, the time complexity for a single merge operation is proportional to O(2M).
- This operation is performed N number of times (to each and every node along the next pointer list) hence the resultant time complexity becomes O(Nx2M).
Space Complexity: O(1) as this code uses no external space or additional data structures to store values. But a recursive stack uses O(N) space to build the recursive calls for each node along the next pointer list.
Frequently Occurring Doubts
Q: Why do we use a Min-Heap instead of sorting all nodes?
A: Sorting all nodes (O(N log N)) would require extracting them into an array, violating in-place constraints. Min-Heap only maintains k elements at a time, making it more memory efficient (O(k) space).
Q: Why is this problem similar to merging k sorted lists?
A: Each child list is already sorted, and we need to merge them efficiently.
Interview Followup Questions
Q: Can we implement this without a heap (O(N log k)) and still be efficient?
A: Yes! Use Divide & Conquer (Recursive Pairwise Merging): Merge two lists at a time until all lists are merged. This reduces extra space usage but keeps the same O(N log k) complexity.
Q: How would this approach change if we had cycles in the child lists?
A: Detect cycles using Floyd’s Cycle Detection (O(n)), then break them before merging.
Notes
Code
✅ Testcase
Input: {'nums': '[[3], [2, 10], [1, 7, 11, 12], [4, 9], [5, 6]]'}
Expected:
1 2 3 4 5 6 7 9 10 11 12
1 2 3 4 5 6 7 9 10 11 12
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[[4, 10], [2, 5, 20], [12, 13, 16, 17]]'}
Expected:
2 4 5 10 12 13 16 17 20
2 4 5 10 12 13 16 17 20
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[[2, 4, 5], [1, 5], [5, 7, 8]]'}
Expected:
1 2 4 5 5 5 7 8
1 2 4 5 5 5 7 8
Actual: -
Time: -
sec
Status: Waiting