Flatten a Linked List with Sorted Bottom Pointers

Given a linked list where every node has two pointers, next and bottom, flatten the structure into one sorted linked list using the bottom pointer.

Each vertical chain connected through bottom is sorted in non-decreasing order. The final list must contain all nodes in sorted order, with next pointers removed or ignored.

Example 1

Input: [[5, 7, 8, 30], [10, 20], [19, 22, 50], [28, 35, 40, 45]]

Output: [5, 7, 8, 10, 19, 20, 22, 28, 30, 35, 40, 45, 50]

Explanation: Every vertical sorted list contributes values to one sorted bottom-linked chain.

Example 2

Input: [[7], [8], [30]]

Output: [7, 8, 30]

Explanation: Single-node vertical chains flatten in sorted order.

Practice it by yourself before moving onto the solutionTry now

Brute Force Approach

In this approach, we ignore the existing sorted structure of the linked list and collect all node values into an array. We traverse each horizontal node using the next pointer and, for every such node, traverse its vertical chain using the bottom pointer.

After collecting all values, we sort the array in non-decreasing order. Then, we create a new linked list using only the bottom pointers and insert the sorted values one by one.

Algorithm

Create an empty array to store all node values, as collecting the values in one place makes it possible to sort them without depending on the existing linked-list structure.
Traverse the horizontal linked list using the next pointer, since each horizontal node represents the starting point of a separate vertical chain.
For every horizontal node, traverse its vertical chain using the bottom pointer, so every node across all vertical lists is included.
Append each visited node's value to the array, ensuring that no value from any vertical chain is missed.
Sort the array in non-decreasing order, as the final bottom-linked list needs to contain values from smallest to largest.
Create a new linked list using the sorted values and connect the nodes through the bottom pointer, since the required output uses the bottom links to represent the sorted chain.
Return the head of the newly created bottom-linked list, as it represents the complete sorted structure.

Dry Run

flatten linkedlist

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    int data;
6    Node* next;
7    Node* bottom;
8
9    Node(int value) {
10        data = value;
11        next = nullptr;
12        bottom = nullptr;
13    }
14};
15
16class Solution {
17public:
18    // Function to flatten the linked list by collecting,
19    // sorting, and rebuilding all node values.
20    Node* flatten(Node* root) {
21        // Store every node value from all bottom chains.
22        vector<int> values;
23
24        // Traverse each vertical linked list.
25        Node* horizontal = root;
26
27        while (horizontal != nullptr) {
28            Node* vertical = horizontal;
29
30            // Collect values from the current bottom chain.
31            while (vertical != nullptr) {
32                values.push_back(vertical->data);
33                vertical = vertical->bottom;
34            }
35
36            // Move to the next vertical linked list.
37            horizontal = horizontal->next;
38        }
39
40        // Sort all collected values.
41        sort(values.begin(), values.end());
42
43        // Dummy node simplifies building the final bottom chain.
44        Node dummy(0);
45        Node* tail = &dummy;
46
47        // Create a new sorted bottom linked list.
48        for (int value : values) {
49            tail->bottom = new Node(value);
50
51            // Advance the tail after attaching the new node.
52            tail = tail->bottom;
53        }
54
55        // Return the head of the flattened linked list.
56        return dummy.bottom;
57    }
58};
59
60// Function to build the linked list from multiple vertical lists.
61Node* buildList(vector<vector<int>>& lists) {
62    // Dummy node simplifies horizontal list construction.
63    Node dummy(0);
64    Node* horizontalTail = &dummy;
65
66    // Build each vertical linked list.
67    for (auto& list : lists) {
68        Node* verticalHead = nullptr;
69        Node* verticalTail = nullptr;
70
71        for (int value : list) {
72            Node* node = new Node(value);
73
74            // Initialize the vertical list.
75            if (verticalHead == nullptr) {
76                verticalHead = node;
77            }
78            // Append the node at the bottom.
79            else {
80                verticalTail->bottom = node;
81            }
82
83            // Update the vertical tail.
84            verticalTail = node;
85        }
86
87        // Attach the completed vertical list horizontally.
88        horizontalTail->next = verticalHead;
89
90        // Advance to the newly attached list.
91        horizontalTail = horizontalTail->next;
92    }
93
94    return dummy.next;
95}
96
97// Function to print the flattened bottom linked list.
98void printFlattened(Node* head) {
99    while (head != nullptr) {
100        cout << head->data;
101
102        if (head->bottom != nullptr) {
103            cout << " ";
104        }
105
106        head = head->bottom;
107    }
108}
109
110// Driver code.
111int main() {
112    vector<vector<int>> lists = {
113        {5, 7, 8, 30},
114        {10, 20},
115        {19, 22, 50},
116        {28, 35, 40, 45}
117    };
118
119    // Build the multi-level linked list.
120    Node* root = buildList(lists);

Complexity Analysis

Time Complexity: O(T log T) T is the total number of nodes across all vertical chains. We traverse all T nodes and then sort their values, which takes O(T log T).

Space Complexity: O(T) The array stores all T node values, and the newly created flattened list also contains T nodes.

Optimal Approach

Since every vertical chain is already sorted, we can use a min heap to always pick the smallest available node among all chains. Initially, we push the head node of every vertical chain into the heap.

Each time, we remove the smallest node from the heap and attach it to the flattened list using the bottom pointer. If the removed node has a bottom child, we push that child into the heap because it may be the next smallest candidate.

This works like merging multiple sorted linked lists and avoids sorting all values together.

Algorithm

Create a min heap ordered by node values, as it keeps the smallest currently available node at the top.
Traverse the horizontal next chain and push every top-level node into the heap, since each one represents the first available node of a sorted vertical chain.
Create a dummy node and a tail pointer for the flattened bottom-linked list, as the dummy node simplifies attaching the first node.
While the heap is not empty, remove the node with the smallest value, since it is the next smallest node among all currently available candidates.
Attach the removed node to tail using the bottom pointer and move tail forward, which extends the flattened list in sorted order.
If the removed node has a bottom child, push it into the heap, as this child is the next available node from that vertical chain.
Continue until the heap becomes empty, ensuring every node has been placed in non-decreasing order.
Set tail->bottom to NULL, as the final node should mark the end of the flattened list.
Return dummy->bottom as the head of the flattened list, since the dummy node is only used to simplify construction.

Dry Run

flatten a ll

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    int data;
6    Node* next;
7    Node* bottom;
8
9    // Constructor for a linked list node.
10    Node(int value) {
11        data = value;
12        next = nullptr;
13        bottom = nullptr;
14    }
15};
16
17class Solution {
18public:
19    // Function to flatten the linked list using a min heap.
20    Node* flatten(Node* root) {
21        // Compare nodes by value so the smallest node stays on top.
22        auto compare = [](Node* first, Node* second) {
23            return first->data > second->data;
24        };
25
26        // Store the current smallest node from every vertical list.
27        priority_queue<Node*, vector<Node*>, decltype(compare)> minHeap(compare);
28
29        // Traverse the horizontal chain.
30        Node* horizontal = root;
31
32        while (horizontal != nullptr) {
33            // Add the head of the current vertical list to the heap.
34            minHeap.push(horizontal);
35
36            // Move to the next vertical list.
37            horizontal = horizontal->next;
38        }
39
40        // Dummy node simplifies construction of the flattened list.
41        Node dummy(0);
42        Node* tail = &dummy;
43
44        // Process nodes until every vertical list is exhausted.
45        while (!minHeap.empty()) {
46            // Extract the smallest available node.
47            Node* smallest = minHeap.top();
48            minHeap.pop();
49
50            // Add the next node from the same vertical chain.
51            if (smallest->bottom != nullptr) {
52                minHeap.push(smallest->bottom);
53            }
54
55            // Attach the smallest node to the flattened bottom chain.
56            tail->bottom = smallest;
57
58            // Move the tail to the newly attached node.
59            tail = tail->bottom;
60
61            // Remove the old horizontal connection.
62            tail->next = nullptr;
63        }
64
65        // Return the head of the flattened linked list.
66        return dummy.bottom;
67    }
68};
69
70// Function to build the linked list from multiple vertical arrays.
71Node* buildList(vector<vector<int>>& lists) {
72    // Dummy node simplifies horizontal list construction.
73    Node dummy(0);
74    Node* horizontalTail = &dummy;
75
76    // Build every vertical linked list.
77    for (auto& list : lists) {
78        Node* verticalHead = nullptr;
79        Node* verticalTail = nullptr;
80
81        for (int value : list) {
82            Node* node = new Node(value);
83
84            // Initialize the current vertical linked list.
85            if (verticalHead == nullptr) {
86                verticalHead = node;
87            } else {
88                // Attach the node at the bottom of the current list.
89                verticalTail->bottom = node;
90            }
91
92            // Update the vertical tail.
93            verticalTail = node;
94        }
95
96        // Attach the completed vertical list horizontally.
97        horizontalTail->next = verticalHead;
98
99        // Move to the newly attached vertical list.
100        horizontalTail = horizontalTail->next;
101    }
102
103    // Return the first horizontal node.
104    return dummy.next;
105}
106
107// Function to print the flattened bottom linked list.
108void printFlattened(Node* head) {
109    while (head != nullptr) {
110        cout << head->data;
111
112        if (head->bottom != nullptr) {
113            cout << " ";
114        }
115
116        // Move to the next node in the bottom chain.
117        head = head->bottom;
118    }
119}
120

Complexity Analysis

Time Complexity: O(T log K) T is the total number of nodes, and K is the number of vertical chains. Each node is processed once through a min heap containing at most K nodes.

Space Complexity: O(K) The min heap stores at most one active node from each of the K vertical chains.

FAQs about Flattening of Linked List

Q1. Can flattening be done without creating new nodes?
Yes. Heap-based and pairwise merge approaches can reuse existing nodes and reconnect nodes through bottom pointers.

Q2. Which pointer should form the final flattened list?
The final sorted chain should use the bottom pointer, while next pointers should be cleared or ignored.

Q3. Does the min heap approach preserve sorted order?
Yes. The heap always extracts the smallest current node among all active vertical chains.

Flatten a Linked List with Sorted Bottom Pointers

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

FAQs about Flattening of Linked List

Read Similar Blogs

Swap Nodes in Pairs

Merge Two Sorted Linked Lists

Find pairs with given sum in Doubly Linked List