Flattening a Linked List | Multiple Approaches with Dry Run

This chapter explores how to flatten a specialized two-dimensional linked list (containing both next and child pointers) into a single vertically sorted linked list. We will examine both the brute-force array-based approach and an optimized recursive in-place merging approach.

1. Problem Statement & Configuration Breakdown

Unlike a standard singly linked list which only utilizes next pointers to traverse horizontally, the linked list in this problem possesses a dual-pointer configuration:

• next pointer: Traverses horizontally across the top-level nodes.
• child (or bottom) pointer: Points vertically downward to a sub-linked list originating from each top-level node.

Key Structural Constraints

• Every individual vertical sub-list is already sorted in ascending order.
• The next pointer of every node in the final flattened list must point to null.
• The final output must be a single vertical linked list linked entirely via child pointers, containing all elements in total sorted order.

2. Naive Approach: Array Collection, Sorting, and Rebuilding

The Intuition & Workflow

The most straightforward approach is to ignore the structural complexity of pointers, extract all integer values into a linear data structure, sort them, and rebuild a brand-new vertical linked list from scratch.

1. Declare an empty list/array to hold all integer values.
2. Maintain a temp pointer at the head and traverse horizontally.
3. For each horizontal node, use a secondary pointer (t2) to traverse downward along the child pointers, pushing every encountered integer into the array.
4. Apply an standard sorting algorithm to the array.
5. Create a new vertical linked list from the sorted array.

Naive Implementation (Pseudo-code)

def flatten_naive(head):
    arr = []
    temp = head
    
    # Step 1: Collect all elements into an array
    while temp is not None:
        t2 = temp
        while t2 is not None:
            arr.append(t2.data)
            t2 = t2.child
        temp = temp.next
        
    # Step 2: Sort the array
    arr.sort()
    
    # Step 3: Convert sorted array into a vertical linked list
    if len(arr) == 0:
        return None
        
    new_head = Node(arr[0])
    curr = new_head
    for i in range(1, len(arr)):
        curr.child = Node(arr[i])
        curr.next = None
        curr = curr.child
        
    curr.next = None
    curr.child = None
    return new_head

Complexity Analysis of Naive Approach

• Time Complexity: $\mathcal{O}(N \cdot M + (N \cdot M) \log(N \cdot M))$, where $N$ is the number of horizontal nodes and $M$ is the average length of each vertical sub-list. The extra term accounts for sorting $N \times M$ total elements.
• Space Complexity: $\mathcal{O}(N \cdot M)$ due to storing elements in the array and allocating brand new nodes for the output linked list.

3. Optimization Strategy: Leveraging Sorted Properties & In-Place Reusability

To optimize our solution, we must eliminate unnecessary external storage and sorting overhead by exploiting two key observations:

1. Vertical Sortedness: Each column is already sorted. We can merge two sorted vertical lists efficiently, analogous to merging two sorted arrays.
2. In-Place Node Reuse: Instead of allocating new memory via new Node(), we can rewire existing node pointers (child and next) directly.

4. Sub-Problem: Merging Two Sorted Vertical Linked Lists

Before merging multiple lists, let's solve the foundational problem: Given two vertically sorted lists (L1 and L2), merge them into a single sorted vertical list using a dummy node.

Core Mental Model: The Dummy Node Anchor

We initialize a dummy node with a placeholder value (e.g., -1) to act as a stable anchor. We compare the heads of L1 and L2, attach the smaller node to our result chain via its child pointer, and advance.

def merge_two_lists(l1, l2):
    dummy_node = Node(-1)
    res = dummy_node
    
    while l1 is not None and l2 is not None:
        if l1.data < l2.data:
            res.child = l1
            res = l1
            l1 = l1.child
        else:
            res.child = l2
            res = l2
            l2 = l2.child
            
    # Attach any remaining elements
    if l1 is not None:
        res.child = l1
    else:
        res.child = l2
        
    # Clean up horizontal next pointers on the dummy anchor
    dummy_node.next = None
    return dummy_node.child

5. Scaling to Multiple Lists via Recursion and Backtracking

To flatten an entire 2D structure of multiple vertical lists, we can apply recursion. We traverse all the way to the rightmost horizontal node (base case), then merge lists backward from right to left as the recursive stack unwinds.

Complete Recursive Flattening Algorithm

def flatten(head):
    # Base case: if head is null or there is no next list to merge with
    if head is None or head.next is None:
        return head
        
    # Recurse down to the right
    head.next = flatten(head.next)
    
    # Merge current list with the already flattened right list
    head = merge_two_lists(head, head.next)
    
    return head

6. Step-by-Step Recursive Dry Run

Let's trace how recursion and backtracking execute on a compact 3-node horizontal chain:

1. Call flatten(node 1): 1.next is not null. Calls flatten(node 4).
2. Call flatten(node 4): 4.next is not null. Calls flatten(node 5).
3. Call flatten(node 5): 5.next is null. Base Case hit! Returns node 5.
4. Backtrack to node 4:
   • Calls merge_two_lists(node 4, node 5).
   • Merges sub-lists 4 -> 9 and 5 -> 6 -> 8.
   • Returns merged head (4).
5. Backtrack to node 1:
   • Calls merge_two_lists(node 1, node 4).
   • Merges sub-list 1 -> 7 -> 11 -> 12 with 4 -> 5 -> 6 -> 8 -> 9.
   • Returns final merged head (1).

7. Comparative Complexity Synthesis

8. Summary and Key Takeaways

• Dual-Pointer Configuration: Recognize structural differences where next moves horizontally across roots and child moves vertically down sorted sub-lists.
• Problem Reduction: Flattening a 2D linked list reduces directly to repeatedly merging two sorted linked lists.
• Dummy Node Utility: Using a dummy node (-1) simplifies edge-case handling when building linked list chains.
• Recursive Backtracking: Traversing to the rightmost node first allows us to merge lists progressively from right to left as we unwind the call stack.
• In-Place Optimization: Reusing existing nodes via pointer manipulation avoids extra heap allocations, optimizing space complexity down to $\mathcal{O}(N)$ stack depth.