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

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!