用递归实现比较简单一点。如果需要完美的one pass则需要写一个helper function，返回flattern后的head和tail.
注意这是双向链表，要把A把B连接到一起，需要同时改两个指针A->next = B, B->prev = A。
时间复杂度：O(n)
空间复杂度：O(n) / stack
|
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 |
class Solution { public: Node* flatten(Node* head) { return solve(head).first; } private: // Flaten head, return new head and new tail. pair<Node*, Node*> solve(Node* head) { if (!head) return {nullptr, nullptr}; Node dummy; Node* cur = &dummy; cur->next = head; while (cur->next) { cur = cur->next; if (cur->child) { auto [h, t] = solve(cur->child); t->next = cur->next; h->prev = cur; if (cur->next) { cur->next->prev = t; } cur->next = h; cur->child = nullptr; } } return {dummy.next, cur}; } }; |