430 Flatten a Multilevel Doubly Linked List

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""
class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        stack = []
        cur = ans = Node(0, None, None, None)
        while head is not None or stack != []:
            if not head:
                head = stack.pop()
            if cur != ans:
                head.prev = cur
            cur.next = head
            cur = cur.next
            if head.child:
                if head.next:
                    stack.append(head.next)
                prev_head = head
                head = head.child
                prev_head.child = None
            else:
                head = head.next
        return ans.next

Java

题解：如果当前点cur 没有child, 直接跳到cur.next 进行下次计算。如果cur 有child, 目标是把cur.child这个level提到cur这个level上。至于cur.child 这个level上有没有点有child 先不管。

算法：

1. cur.child 一直只按next找到tail；
2. 这一节插在cur 和 cur.next之间；
3. cur再跳到更新的cur.next上.

Time Complexity: O(n) n是所有点的个数, 每个点只走过constant次数.

Space: O(1)

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
    public Node flatten(Node head) {
        if(head == null)
            return head;
        Node cur = head;
        while(cur != null){
            if (cur.child == null){
                cur = cur.next;
                continue;
            }
            Node child = cur.child;
            Node childTail = child;
            while(childTail.next != null){
                childTail = childTail.next;
            }
            cur.child = null;
            child.prev = cur;
            childTail.next = cur.next;
            if(cur.next != null){
                cur.next.prev = childTail;
            }
            cur.next = child;
            cur = cur.next;
        }
        return head;
    }
}