Flatten a Linked List

geeksforgeeks.org

Problem that secretly tests whether you can recognize Merge K Sorted Lists hidden behind a different structure.

---

Problem Statement

We are given a linked list where:

• next pointer connects different linked lists horizontally.
• bottom pointer connects nodes vertically.
• Every vertical list is already sorted.

Our task is to flatten the entire structure into a single sorted linked list using only the bottom pointer.

Example

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

Output:

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

---

Brute Force Intuition

The most straightforward approach is:

1. Traverse all nodes.
2. Store values inside an array.
3. Sort the array.
4. Rebuild the linked list.

How to Explain in an Interview

Since all nodes are accessible through next and bottom pointers, we can collect every value into a list, sort it, and create a new flattened linked list. Although simple, this approach doesn't utilize the fact that individual bottom lists are already sorted.

Complexity

Time Complexity  : O(N log N)
Space Complexity : O(N)

where N is the total number of nodes.

---

Observation That Changes Everything

Notice something important:

Every bottom linked list is already sorted.

That means we're unnecessarily sorting data again.

Instead of:

Collect → Sort → Rebuild

we can directly:

Merge Sorted Lists

This suddenly becomes very similar to:

Merge K Sorted Linked Lists

And whenever you hear that phrase, a merge-based solution should immediately come to mind.

---

Optimal Approach

Core Idea

Flatten the linked list from right to left.

Imagine:

5 -> 10 -> 19 -> 28

We first flatten:

19 -> 28

Then merge the result with:

10

And finally merge everything with:

5

At every stage, we only merge two sorted linked lists.

---

Algorithm

Step 1

Flatten all lists on the right.

root.next = flatten(root.next);

Step 2

Merge current list with the already flattened right side.

return merge(root, root.next);

Step 3

Use standard merge logic of two sorted linked lists.

Compare values and connect nodes through bottom pointers.

---

Java Solution

class Solution {

    public Node flatten(Node root) {

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

        root.next = flatten(root.next);

        return merge(root, root.next);
    }

    private Node merge(Node a, Node b) {

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

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

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

            current = current.bottom;
            current.next = null;
        }

        if (a != null) {
            current.bottom = a;
        } else {
            current.bottom = b;
        }

        return dummy.bottom;
    }
}

---

Dry Run

Input:

5 -> 10 -> 19

5 -> 7 -> 8 -> 30

10 -> 20

19 -> 22 -> 50

First Merge

10 -> 20

with

19 -> 22 -> 50

Result:

10 -> 19 -> 20 -> 22 -> 50

Second Merge

5 -> 7 -> 8 -> 30

with

10 -> 19 -> 20 -> 22 -> 50

Result:

5 -> 7 -> 8 -> 10 -> 19 -> 20 -> 22 -> 30 -> 50

Flattened and sorted.

---

Why This Works

The recursion guarantees that:

flatten(root.next)

always returns a sorted flattened list.

So after recursion, the problem reduces to:

Merge Two Sorted Linked Lists

And that's a problem we've already solved many times.

The beauty of this question is not the code.

The beauty is recognizing the pattern hiding underneath.

---

Pattern Recognition

Whenever a problem contains:

• Multiple sorted lists
• Need one final sorted list
• Merge operation available

Think:

Merge K Sorted Lists

This question is simply that pattern wearing a Linked List disguise.

---

Complexity Analysis

Let:

• N = Total Nodes
• K = Number of vertical linked lists

Time Complexity

O(N × K)

Space Complexity

O(K)

Recursive stack space.

---

Interview Takeaway

Most candidates see a complicated linked list structure.

Strong candidates see:

"A collection of sorted linked lists waiting to be merged."

The moment you identify that pattern, the entire problem becomes a standard merge exercise.