Subject to introduce

Buckle 430: leetcode-cn.com/problems/fl…

Analysis of the

According to the question, all we need to do is find the node that contains the child list, disconnect the list from here, attach the child list, and then attach the last node of the child list to the next node before the current node. The details are shown in the figure below:The sequence of processing nodes of iteration is as follows:

However, since the linked list itself does not have a loop, the construction order of “iterations” is adjusted to ensure that each node is accessed a constant number of times.

The code is as follows:

/* // 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) {
        tranverse(head);
        return head;
    }

    public void tranverse(Node head) {
        if(head == null) {
            return;
        }
        while(head ! =null) {
            // Find the node with the child list
            if(head.child ! =null) {
                // First save the next node of the current node
                Node nextNode = head.next;
                // The next pointer to the current node points to the child nodes
                head.next = head.child;
                // The child's prev pointer points to the current node
                head.child.prev = head;
                // Sets the child node pointer of the current node to null
                head.child = null;
                Node cur = head;
                // Traverses all the children below the current node to find the last node in the child list
                while(cur.next ! =null) {
                    cur = cur.next;
                }
                // The last node of the child list points to the next node before the current one
                cur.next = nextNode;
                if(nextNode ! =null) { nextNode.prev = cur; } } head = head.next; }}}Copy the code