Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

430. Flat multilevel bidirectional linked lists

In a multi-level bidirectional list, in addition to the pointer to the next node and the previous node, it has a child list pointer that may point to a separate bidirectional list. These sublists may also have one or more subitems of their own, and so on, generating multi-level data structures, as shown in the following example.

Given the head node at the first level of the list, flatten the list so that all nodes appear in a single level double-linked list.

Thought analysis

Please flatten the list so that all nodes appear in a single level double linked list. However, it can be understood that all points need to be traversed once. However, since there is no clear traversal method in the question, we choose to try our best to get the answer from the examples given by the question.

The way they’re going to traverse looks like a depth-first traverse of the child, so we have

Node tmp = node; // For a node node
/ / record next
// Check if there is a child
// Next

// Repeat the above process
Copy the code
Node tmp = node; // For a node node
/ / record next
next = tmp - > next;
// Check if there is a child
if(tmp->child ! = null){ tmp->next =dfs(tmp -> child)
    c = tmp->next;
    c -> pre = tmp;
    tmp = c;
    
}

// Next

if(next ! = null){ tmp->next = next; tmp->next->pre = tmp; tmp = tmp -> next; }//
Copy the code

All you need to do to repeat this process is add a while loop.