Flattening a Linked List

Problem Summary

This is a very important linked list + merge pattern problem.

You are given a linked list where:

• next → connects main nodes

• bottom → connects sorted sub-linked lists

Each bottom list is already sorted.

Your task:

Flatten everything into one sorted linked list using only bottom pointers

Key Insight

This is NOT a traversal problem.

This is a merge k-sorted linked lists problem.

Because:

• Each vertical list is sorted

• We repeatedly merge lists

Optimal Idea

We use divide and conquer (merge sort style):

Step 1

Flatten next list recursively

Step 2

Merge two sorted bottom-linked lists

Core Operation: Merge 2 Lists

We merge like:

• Compare nodes

• Attach smaller node to result

• Move pointers

Approach

Function 1:

flatten(root)
→ flatten(root.next)
→ merge(root, root.next)

Function 2:

merge(a, b)
→ sorted merge using bottom pointers

Example Intuition

5 → 10 → 19
↓ ↓ ↓
7 20 22
↓
8

Flatten step by step:

• 5 list + 10 list → merged

• Then merge with 19 list → final sorted list

Java Solution

class Solution {

    Node merge(Node a, Node b) {

        Node dummy = new Node(0);
        Node temp = dummy;

        while (a != null && b != null) {

            if (a.data < b.data) {
                temp.bottom = a;
                a = a.bottom;
            } else {
                temp.bottom = b;
                b = b.bottom;
            }

            temp = temp.bottom;
        }

        if (a != null) temp.bottom = a;
        else temp.bottom = b;

        return dummy.bottom;
    }

    public Node flatten(Node root) {

        if (root == null || root.next == null)
            return root;

        // flatten right side
        root.next = flatten(root.next);

        // merge current and right
        root = merge(root, root.next);

        return root;
    }
}

Complexity

• Time Complexity: O(n × m)

  • n = number of main nodes

  • m = nodes per list

• Space Complexity: O(n) (recursion stack)

Key Takeaways

• This is a merge-based linked list problem

• Treat each vertical list as a sorted list

• Always use:

  • Merge + Recursion (divide and conquer)

Pattern Recognition

If you see:

• Multiple sorted linked lists

• Vertical + horizontal pointers

• Flattening structure

Think:

Merge K Sorted Lists Pattern

Summary

This problem demonstrates how to flatten a complex linked list structure by treating each vertical list as a sorted list and applying a divide-and-conquer merge strategy. By recursively flattening and merging, the entire structure is converted into a single sorted list using bottom pointers.