leetcode

0 class Solution {

1 void insert_after(Node **t, Node *n) {

2 n->prev = *t;

3 n->child = nullptr;

4 (*t) = (*t)->next = n;

5 }

6

7 public:

8 Node *flatten(Node *head) {

9 if (!head) return nullptr;

10

11 stack<Node *> s;

12 s.push(head);

13

14 Node *h, *t;

15 t = h = new Node();

16 while (!s.empty()) {

17 Node *self = s.top();

18 s.pop();

19 if (self->next) s.push(self->next);

20 Node *child = self->child;

21 insert_after(&t, self);

22 while (child) {

23 self = child;

24 child = self->child;

25 insert_after(&t, self);

26 if (self->next) s.push(self->next);

27 }

28 }

29 t->next = nullptr;

30 h->next->prev = nullptr;

31 return h->next;

32 }

33 };