700192. Flattening a Linked List
Flattening a Linked List
Slug: flattening-a-linked-list
Difficulty: Medium
Id: 700192
Topic Tags: Linked List, Data Structures
Company Tags: Paytm, Flipkart, Amazon, Microsoft, Snapdeal, 24*7 Innovation Labs, Payu, Visa, Goldman Sachs, Qualcomm, Drishti-Soft
Summary
Flattening a linked list involves transforming a multi-level linked list into a single-level linked list. This problem requires the ability to traverse and manipulate linked lists, making it a great exercise in understanding data structures.
Detailed Explanation
A multi-level linked list is a list where each node contains another linked list as its next element. The goal of this problem is to flatten such a list into a single-level linked list where all nodes are at the same level.
Here's an algorithmic approach to solve this problem:
- Create a new head pointer for the flattened list.
- Initialize a current pointer to the head of the original list.
- Traverse the original list and for each node, recursively call a function that flattens the linked list contained in the node.
- While traversing the original list, also consider the nodes that are not part of any sub-lists (i.e., leaf nodes). These nodes should be added to the flattened list directly.
Here's a step-by-step breakdown of the solution:
- Start at the head of the original linked list.
- If the current node is not null and it's not the last node in the list, add it to the flattened list.
- Move to the next node in the original list.
- Repeat steps 2-3 until you've traversed the entire original list.
Here's an ASCII art diagram of a multi-level linked list:
1 -> [2 -> 3] -> [4 -> 5]
|
|--6
The flattened linked list would look like this:
1 -> 2 -> 3 -> 4 -> 5 -> 6
Time complexity for this solution is O(n), where n is the number of nodes in the original linked list. Space complexity is O(1) as we're not using any extra space that scales with input size.
Optimized Solutions
Java
class Node {
int data;
Node next, child;
public Node(int d) {
data = d;
next = null;
child = null;
}
}
class FlattenLinkedList {
static Node flatten(Node head) {
if (head == null)
return null;
Node curr = head;
while (curr != null) {
if (curr.child != null) {
Node last = curr;
while (last.next != null)
last = last.next;
last.next = curr.child;
curr.child = null;
}
curr = curr.next;
}
return head;
}
}