Flatten a Multilevel Doubly Linked List leetcode

Question

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

class Solution {
/*Global variable pre to track the last node we visited */
    Node pre = null;
    public Node flatten(Node head) {
        if (head == null) {
            return null; 
        }
/*Connect last visted node with current node */
        if (pre != null) {
            pre.next = head; 
            head.prev = pre;
        }

        pre = head; 
/*Store head.next in a next pointer in case recursive call to flatten head.child overrides head.next*/
        Node next = head.next; 

        flatten(head.child);
        head.child = null;

        flatten(next);        
        return head; 
    }
}

For the question, the above leetcode solution works. But I don't understand this:

/*Store head.next in a next pointer in case recursive call to flatten head.child overrides head.next*/
        Node next = head.next;

Can anyone explain this part? How does the head.child override head.next?

Muhteva Muhteva · Accepted Answer · 2021-08-28T12:08:02

flatten(head.child) may change head.next due to the part where we connect last visited node with the current node:

if (pre != null) {
  pre.next = head; 
  head.prev = pre;
}

At this stage, pre represents older head and head represents head.child. So we actually connect our head with its child. But if we do so, we will lose our connection to the actual head.next, therefore we have to keep it in an extra variable called next. That's why we keep it before calling the flatten() function.

Flatten a Multilevel Doubly Linked List leetcode

1 Answers