Sword finger offer II 028 Flatten multi-level bidirectional linked list

Summary

With the help of the stack to save the child linked list nodes next node

subject

In the multi-level bidirectional linked list , In addition to pointing to the next node and the previous node pointer , It also has a child list pointer , It may point to a separate double linked list . These sublists may also have one or more of their own , And so on , Generate multilevel data structures , As the following example shows .

Give the header node positioned at the first level of the list , Please flatten the list , That is to flatten such a multi-level two-way linked list into an ordinary two-way linked list , Make all nodes appear in a single level double linked list .

link ：https://leetcode.cn/problems/Qv1Da2

Ideas

The topic is so complicated , Blind .

Think again and again , It is actually traversing from the beginning , If there is a sub linked list , If the sub linked list is traversed , Find your own parent node according to the previous pointer , The next The node is hung to the end of the newly generated linked list . Of course , Here, you also need to maintain the pointer of the previous node .

The whole operation is very troublesome .

We can use the stack , Once you encounter a node that has a child linked list , Will next Nodes are pushed onto the stack . Once a sub linked list comes to an end , Out of the stack , And hang the nodes in the stack behind the last node in the sub linked list , And point the front pointer of the stack node to the last node .

solution ： With the help of the stack to save the child linked list nodes next node

Code

public Node flatten(Node head) {
    
    Stack<Node> stack = new Stack<>();
    Node dummy = new Node();
    dummy.next = head;
    while (head != null) {
    
        if (head.child != null) {
    
            //  If the next node is empty , No need to stack 
            if (head.next != null) {
    
                stack.push(head.next);
            }
            //  Here we need to pay attention to dealing with the front and back pointers 
            head.next = head.child;
            head.child.prev = head;
            Node temp = head.child;
            //  Because as long as the simple two-way linked list , therefore child And get rid of 
            head.child = null;
            head = temp;
            continue;
        }

        if (head.next != null) {
    
            head = head.next;
        } else if (!stack.isEmpty()) {
    
            Node pop = stack.pop();
            //  Here we need to pay attention to dealing with the front and back pointers 
            head.next = pop;
            pop.prev = head;
            head = pop;
        } else {
    
            break;
        }
    }
    return dummy.next;
}