Original address: leetcode-cn.com/problems/fl… Repo address: github.com/pigpigever/…

We have to figure out what the problem is first and then try to solve it. In fact, most of the linked list problems are not difficult, the best before writing code to draw on paper, the idea will be a lot clearer.

Topic analysis 🧐

The title describes a linked list with such a structure:

function Node(val,prev,next,child) {
    this.val = val;
    this.prev = prev;
    this.next = next;
    this.child = child;
}
Copy the code

So it’s not just a bidirectional linked list, it might have sub-linked lists

Let’s take a look at the official input and output example 👇

Input:

 1--2 ---- 3--4 ---- 5--- 6--NULL
         |
         7--- 8 ---9 ---- 10--NULL
             |
             11-- 12--NULL
Copy the code

Output:

12 -- 37 -- 8 -- 11- 129 -- 104 -- 5- 6-NULL
Copy the code

The flattening step can be viewed as follows:

The first step:

 1--2 ---- 3--4 ---- 5--- 6--NULL
         |
         7--- 8 ---- 11--- 12--9 ---- 10--NULL
Copy the code

The second step:

1--2 ---- 3--7 ---- 8 ---- 11--- 12--9 ---- 10--4 ---- 5--- 6--NULL
Copy the code

Obviously, we need to recursively process the child list and concatenate it with the parent list.

Combing logic 💡

After analyzing the topic, we will comb the logic 👇

  • Find the child list and concatenate it to the next node in the parent list
  • If there are child lists, the child lists are processed first

The concatenation logic can be further refined as follows 👇

  • Saves the first node of the sublist
  • Saves the previous node of the child list and the next node of this node
  • Saves the last node of the sublist
  • With the first and last nodes and the first and last nodes of the child list, you can join the child list to the parent list

Example code 🌰

/** * @param {Node} head * @return {Node} */
var flatten = function(head) {
    dfs(head)
    function dfs (head) {
        let target = head, pre = null, last = null
        while (target) {
            let next = target.next, child = target.child
            if (child) {
                target.next = child
                child.prev = target
                target.next = child
                last = dfs(child)
                last.next = next
                pre = last
                target.child = null
                if (next) {
                    next.prev = last
                }
            } else {
                pre = target
            }
            target = next
        }
        return pre
    }
    return head
};
Copy the code

One caveat, of course, is that the next, prev, and Child Pointers can all be null, and you need to take these into account when writing code.

Write at the end 🔚

I have been brushing questions on LeetCode and joined the organization before. If you are interested in learning together, you can leave a message below or follow my wechat public account “Tony’s Front-end Cram School” and leave a message in the background. You can join the group to learn with the big guys.