Data Structure Linked List: Flattening a Linked List

http://www.geeksforgeeks.org/flattening-a-linked-list/
 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <stack>
 6 #include <string>
 7 #include <fstream>
 8 #include <map>
 9 #include <set>
10 using namespace std;
11 
12 struct node {
13     int data;
14     node *right;
15     node *down;
16     node(int d = 0) : data(d), right(NULL), down(NULL) { }
17 };
18 
19 struct cmp {
20     bool operator() (node *a, node *b) {
21         return a->data > b->data;
22     }
23 };
24 
25 void push(node* &head, int k) {
26     node *new_node = new node(k);
27     new_node->down = head;
28     head = new_node;
29 }
30 
31 node* flatten(node *&root) {
32     priority_queue<node*, vector<node*>, cmp> S;
33     while (root) {
34         S.push(root);
35         root = root->right;
36     }
37     root = NULL;
38     node *p;
39     while (!S.empty()) {
40         node *top = S.top();
41         S.pop();
42         if (!root) {
43             root = top;
44             p = top;
45         }
46         else {
47             p->right = top;
48             p = p->right;
49         }
50         if (top->down) S.push(top->down);
51     }
52     return root;
53 }
54 
55 void print(node *head) {
56     while (head) {
57         cout << head->data << " ";
58         head = head->right;
59     }
60 }
61 
62 int main() {
63     node *root = NULL;
64     push( root, 30 );
65     push( root, 8 );
66     push( root, 7 );
67     push( root, 5 );
68 
69     push( ( root->right ), 20 );
70     push( ( root->right ), 10 );
71 
72     push( ( root->right->right ), 50 );
73     push( ( root->right->right ), 22 );
74     push( ( root->right->right ), 19 );
75 
76     push( ( root->right->right->right ), 45 );
77     push( ( root->right->right->right ), 40 );
78     push( ( root->right->right->right ), 35 );
79     push( ( root->right->right->right ), 20 );
80 
81     root = flatten(root);
82     print(root);
83     return 0;
84 }