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.