LC.P430[扁平化多级双向链表]

方法一：迭代

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
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        Node dummy = new Node();
        for (dummy.next = head; head != null; head = head.next) {
            if (head.child != null) {
                Node temp = head.next;
                Node child = head.child;
                head.next = child;
                child.prev = head;
                head.child = null;
                Node cur = head;
                while (cur.next != null) cur = cur.next;
                cur.next = temp;
                if (temp != null) temp.prev = cur;
            }
        }
        return dummy.next;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$