Flatten a Linked List

Problem Statement

Given a linked list where every node has two pointers: next pointing to the next node and down pointing to a linked list where this node is the head. All linked lists are sorted. Flatten the list into a single sorted linked list using the down pointer.

Example

Input:
5 -> 10 -> 19 -> 28
|    |     |     |
7    20    22    35
|          |     |
8          50    40
|                |
30               45

Output: 5 -> 7 -> 8 -> 10 -> 19 -> 20 -> 22 -> 28 -> 30 -> 35 -> 40 -> 45 -> 50

Brute Force Approach

Intuition

The brute force approach collects all values from all nodes (following both next and down pointers), sorts them, and creates a new flattened list.

Algorithm

Traverse all nodes using both next and down pointers
Collect all values in an array
Sort the array
Create a new linked list with sorted values

Code

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Node {
    int data;
    Node next;
    Node down;
    
    Node(int data) {
        this.data = data;
        this.next = null;
        this.down = null;
    }
}

public class FlattenListBrute {
    public static Node flattenBruteForce(Node head) {
        if (head == null) return null;
        
        List<Integer> values = new ArrayList<>();
        
        // Collect all values
        Node curr = head;
        while (curr != null) {
            Node down = curr;
            while (down != null) {
                values.add(down.data);
                down = down.down;
            }
            curr = curr.next;
        }
        
        // Sort all values
        Collections.sort(values);
        
        // Create new flattened list
        Node newHead = new Node(values.get(0));
        Node tail = newHead;
        
        for (int i = 1; i < values.size(); i++) {
            tail.down = new Node(values.get(i));
            tail = tail.down;
        }
        
        return newHead;
    }
    
    public static void printFlattened(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.down != null) System.out.print(" -> ");
            head = head.down;
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity: O(n * m * log(n * m)) where n is number of horizontal nodes and m is average down list length
Space Complexity: O(n * m) to store all values

Optimal Approach

Intuition

Since all individual down lists are already sorted, we can use merge sort's merge technique. We recursively flatten from right to left, merging two sorted lists at a time.

Algorithm

Recursively flatten the list starting from the rightmost node
For each node, merge its down list with the already flattened right portion
Use the standard sorted list merge technique
Return the head of the flattened list

Code

java

class Node {
    int data;
    Node next;
    Node down;
    
    Node(int data) {
        this.data = data;
        this.next = null;
        this.down = null;
    }
}

public class FlattenListOptimal {
    // Merge two sorted lists
    public static Node mergeSorted(Node a, Node b) {
        if (a == null) return b;
        if (b == null) return a;
        
        Node result;
        
        if (a.data < b.data) {
            result = a;
            result.down = mergeSorted(a.down, b);
        } else {
            result = b;
            result.down = mergeSorted(a, b.down);
        }
        
        result.next = null;
        return result;
    }
    
    public static Node flattenOptimal(Node head) {
        // Base case
        if (head == null || head.next == null) {
            return head;
        }
        
        // Recursively flatten the rest of the list
        head.next = flattenOptimal(head.next);
        
        // Merge current list with flattened list
        head = mergeSorted(head, head.next);
        
        return head;
    }
    
    public static void printFlattened(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.down != null) System.out.print(" -> ");
            head = head.down;
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        // Create the structure
        Node head = new Node(5);
        head.down = new Node(7);
        head.down.down = new Node(8);
        head.down.down.down = new Node(30);
        
        head.next = new Node(10);
        head.next.down = new Node(20);
        
        head.next.next = new Node(19);
        head.next.next.down = new Node(22);
        head.next.next.down.down = new Node(50);
        
        head.next.next.next = new Node(28);
        head.next.next.next.down = new Node(35);
        head.next.next.next.down.down = new Node(40);
        head.next.next.next.down.down.down = new Node(45);
        
        System.out.print("Flattened list: ");
        head = flattenOptimal(head);
        printFlattened(head);
    }
}

Complexity Analysis

Time Complexity: O(n * m) where n is number of horizontal nodes and m is average down list length
Space Complexity: O(n) for recursion stack (can be O(1) with iterative merge)

Key Takeaways

Leverage Sorted Property: Since down lists are sorted, use merge instead of general sorting
Right-to-Left Processing: Flatten from right to left to avoid complex pointer management
Merge Pattern: The same merge technique from merge sort applies here
Recursive Structure: The recursive solution elegantly handles arbitrary depth
Pointer Management: After merging, set next to null as we're using down for the flattened list
Space Optimization: The iterative merge can achieve O(1) extra space
Similar Problems: This pattern applies to multi-level data structures like skip lists