[leetcode] flat multi-level bidirectional linked list

#LeetCode A daily topic 【 Special topic of linked list 】

• Multi level flat list
  https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/
• analysis
  The description of the topic is rather complicated , But after understanding it , The general meaning is to traverse the subset linked list first , Traverse backward ; Basically, you can think of using recursion , Judge whether the node has child, There is a recursive call to itself , If not, go straight down . After recursion , Insert the results into the previous linked list .
• Realization

	public Node flatten(Node head) {
    
        Node node = head, next;
        while (node != null) {
    
            next = node.next;
            if (node.child != null) {
    
                Node child = flatten(node.child);
                //  find child Last element of 
                Node temp = child;
                while (temp.next != null) {
    
                    temp = temp.next;
                }
                //  take child Insert node Back 
                temp.next = next;
                if (next != null) {
    
                    // next May is empty , And no longer need to maintain its prev
                    next.prev = temp;
                }
                node.next = child;
                child.prev = node;
                //  Disconnect the child 
                node.child = null;
            }
            node = next;
        }
        return head;
    }

LeetCode Time consuming ：0ms

• Optimize
  After that, I read the following explanation , You can remove the last node of the list every time you look for it , Enable another method to use recursion , It returns the last node of the linked list after each processing

	public Node flatten02(Node head) {
    
        //  Optimize ： Restart a method to start recursion , Return it to the last node after processing , Facilitate splicing ;; Avoid the same as above , Find the last node from the beginning 
        dfs(head);
        return head;
    }

    private Node dfs(Node head) {
    
        Node node = head, next, last = null;
        while (node != null) {
    
            next = node.next;
            if (node.child != null) {
    
                Node childLast = dfs(node.child);
                // childLast yes child Last element of 
                //  take child Insert node Back 
                childLast.next = next;
                if (next != null) {
    
                    // next May is empty , And no longer need to maintain its prev
                    next.prev = childLast;
                }
                node.next = node.child;
                node.child.prev = node;
                //  After that , The last node of the linked list on the splice is childLast
                last = childLast;
                //  Disconnect the child 
                node.child = null;
            } else {
    
                last = node;
            }
            node = next;
        }
        return last;
    }

It's all the same , You just need to find the tail node of the linked list and return
LeetCode Time consuming ：0ms

• summary
  Something like this involves deep traversal , Consider using recursion to handle , Think about what will be returned after recursion , Got the return result , What needs to be done with the current element . Finally, just pay attention to the details .

• Last
  LeetCode Special topic of linked list , Completed 31. Next month, we will start the next topic , Binary tree ~