Given a list which can grow in both horizontal and vertical directions (right and down), flatten it into a singly linked list. The conversion should be in such a way that down node is processed before the next node for any node.

This list is similar to the standard linked list except that it has one extra field *down* which points to a vertical list. The vertical list can have horizontal list attached to it and vice versa.

The Flattened list would be:

`1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> null`

The idea is to use Recursion. We can recursively flatten a linked list by recursively flattening the down list first, followed by the next list. The flattened down list for a node is linked to the next pointer of that node, while the flattened next list for a node is linked to the next pointer of the last seen node.

This can be implemented as follows in C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <iostream> using namespace std; // Data structure to represent a special linked list node with // an additional down pointer struct Node { int data; Node* next; Node* down; Node(int data) { this->data = data; this->next = this->down = nullptr; } }; // Utility function to print a list with down and next pointers void printOriginalList(Node* head) { if (head == nullptr) return; cout << ' ' << head->data << ' '; if (head->down) { cout << "["; printOriginalList(head->down); cout << "]"; } printOriginalList(head->next); } // Utility function to print a linked list void printFlatenedList(Node* head) { while (head) { cout << head->data << " -> "; head = head->next; } cout << "null" << '\n'; } // Recursive function to flatten a multilevel linked list Node* flattenList(Node* head) { // base case if (head == nullptr) return nullptr; // keep track of the next pointer Node* next = head->next; // process the down list first head->next = flattenList(head->down); // go to the last node Node* tail = head; while (tail->next) { tail = tail->next; } // process the next list after the down list tail->next = flattenList(next); // return head node return head; } // main function int main() { // create individual nodes first and link them together later Node* one = new Node(1); Node* two = new Node(2); Node* three = new Node(3); Node* four = new Node(4); Node* five = new Node(5); Node* six = new Node(6); Node* seven = new Node(7); Node* eight = new Node(8); Node* nine = new Node(9); Node* ten = new Node(10); Node* eleven = new Node(11); Node* twelve = new Node(12); Node* thirteen = new Node(13); Node* fourteen = new Node(14); Node* fifteen = new Node(15); // set head node Node* head = one; // set next pointers one->next = four; four->next = fourteen; fourteen->next = fifteen; five->next = nine; nine->next = ten; seven->next = eight; eleven->next = thirteen; // set down pointers one->down = two; two->down = three; four->down = five; five->down = six; six->down = seven; ten->down = eleven; eleven->down = twelve; cout << "The Original list is :" << '\n'; printOriginalList(head); head = flattenList(head); cout << "\n\nThe Flattened list is :" << '\n'; printFlatenedList(head); return 0; } |

`Output:`

The Original list is :

1 [ 2 [ 3 ]] 4 [ 5 [ 6 [ 7 8 ]] 9 10 [ 11 [ 12 ] 13 ]] 14 15

The Flattened list is :

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> null

The time complexity of above solution is `O(n)` and requires `O(n)` space for the call stack. We can further optimize the code by maintaining a tail pointer as we move along. This is demonstrated here.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

+1