Flatten a Multilevel Doubly Linked List

▶

Steps

setup

Initialize traversal at head node 1

Start with the head node (value 1). The current pointer is set to node 1, and the stack shows the traversal starting point.

💡 Initialization sets the starting point for flattening, making clear where the algorithm begins.

Line:

curr = head

💡 The algorithm begins traversal from the head node, preparing to scan for child pointers.

traverse

Move to node 2 (no child)

Move the current pointer from node 1 to node 2. Node 2 has no child, so no splicing occurs.

💡 Each move forward checks for children; no child means simple traversal.

Line:

curr = curr.next

💡 Traversal advances linearly when no child is present.

traverse

Move to node 3 (child detected)

Current pointer moves to node 3, which has a child pointer to node 7. The algorithm prepares to flatten this child list.

💡 Detecting a child triggers the flattening process at this node.

Line:

if curr.child:

💡 Child pointers indicate sublists that must be integrated into the main list.

expand

Find tail of child list starting at node 7

Traverse the child list starting at node 7 to find its tail node (node 10). This tail will be connected to node 4.

💡 Finding the tail is essential to reconnect the flattened child list back to the main list.

Line:

tail = child
while tail.next:
    tail = tail.next

💡 The tail node marks where the child list ends and where to reconnect the main list.

insert

Connect tail node 10 to node 4

Connect the tail of the child list (node 10) to node 4, preserving the original next nodes after node 3.

💡 This connection ensures the flattened child list links back to the main list seamlessly.

Line:

if curr.next:
    tail.next = curr.next
    curr.next.prev = tail

💡 Re-linking the tail to the next node maintains list continuity after splicing.

insert

Splice child list starting at node 7 after node 3

Set node 3's next pointer to its child (node 7) and update child's prev pointer to node 3, effectively splicing the child list in.

💡 Splicing inserts the entire child list directly after the current node.

Line:

curr.next = child
child.prev = curr
curr.child = None

💡 Removing the child pointer after splicing prevents reprocessing and marks the list as flattened at this node.

traverse

Move to node 7 (child of node 3)

Traverse into the newly spliced child list starting at node 7, which has no child pointer itself.

💡 Traversal continues into the child list to check for further children.

Line:

curr = curr.next

💡 The algorithm handles nested children by continuing traversal into spliced lists.

traverse

Move to node 8 (child detected)

At node 8, detect a child pointer to node 11, triggering flattening of this nested child list.

💡 Nested children require the same flattening steps recursively.

Line:

if curr.child:

💡 The algorithm handles multiple levels by repeating the flattening process.

expand

Find tail of nested child list starting at node 11

Traverse the nested child list starting at node 11 to find its tail node (node 12).

💡 Finding the tail allows reconnecting the nested child list back to node 9.

Line:

tail = child
while tail.next:
    tail = tail.next

💡 Tail node marks the end of the nested child list for reconnection.

insert

Connect tail node 12 to node 9

Connect the tail of the nested child list (node 12) to node 9, preserving the original next nodes after node 8.

💡 This connection maintains list continuity after splicing the nested child list.

Line:

if curr.next:
    tail.next = curr.next
    curr.next.prev = tail

💡 Re-linking the tail to the next node maintains list continuity after splicing nested children.

insert

Splice nested child list starting at node 11 after node 8

Set node 8's next pointer to its child (node 11) and update child's prev pointer to node 8, splicing the nested child list in.

💡 Splicing inserts the nested child list directly after node 8.

Line:

curr.next = child
child.prev = curr
curr.child = None

💡 Removing the child pointer after splicing prevents reprocessing nested children.

traverse

Traverse nodes 11 and 12 (no children)

Move through nodes 11 and 12 sequentially; neither has children, so traversal continues linearly.

💡 Nodes without children are traversed without modification.

Line:

curr = curr.next

💡 Traversal proceeds through flattened child lists smoothly.

traverse

Move to node 12

Advance current pointer to node 12, continuing traversal through the flattened nested child list.

💡 Traversal continues until the end of the nested child list.

Line:

curr = curr.next

💡 Traversal moves forward through all nodes in the flattened list.

traverse

Move to node 9 (continuing after nested child list)

After finishing nested child list, move to node 9, which has no child pointer.

💡 Traversal resumes at the node following the spliced nested child list.

Line:

curr = curr.next

💡 Flattening preserves original next nodes after child lists.

traverse

Move to node 10 (no child)

Traverse to node 10, the tail of the first child list, which has no child pointer.

💡 Traversal continues linearly through the flattened child list.

Line:

curr = curr.next

💡 Traversal covers all nodes in the spliced child list.

traverse

Move to node 4 (continue main list after child)

After finishing the child list, move to node 4, continuing traversal on the main list.

💡 Traversal resumes on the main list after splicing child lists.

Line:

curr = curr.next

💡 Flattening preserves the original order after child lists.

traverse

Traverse nodes 5 and 6 (no children)

Traverse nodes 5 and 6 sequentially; neither has children, so traversal continues to the end.

💡 Traversal completes the main list after flattening all children.

Line:

curr = curr.next

💡 Traversal finishes at the end of the flattened list.

traverse

Move to node 6 (end of list)

Move to node 6, the last node in the list, which has no child pointer.

💡 Traversal reaches the end of the list.

Line:

curr = curr.next

💡 Traversal ends when current pointer becomes null after last node.

reconstruct

Traversal complete, return flattened list head

Current pointer is now null, indicating traversal and flattening are complete. Return the head node as the flattened list.

💡 Returning the head provides access to the fully flattened list.

Line:

return head

💡 The algorithm completes with a fully flattened list accessible from the original head.

class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

def flatten(head):
    curr = head  # STEP 1: Initialize traversal
    while curr:
        if curr.child:  # STEP 3,8: Child detected
            child = curr.child
            tail = child
            while tail.next:  # STEP 4,9: Find tail of child list
                tail = tail.next
            if curr.next:  # STEP 5,10: Connect tail to curr.next
                tail.next = curr.next
                curr.next.prev = tail
            curr.next = child  # STEP 6,11: Splice child list
            child.prev = curr
            curr.child = None
        curr = curr.next  # STEP 2,7,12-18: Move to next node
    return head  # STEP 19: Return flattened list head

📊

Flatten a Multilevel Doubly Linked List - Watch the Algorithm Execute, Step by Step

Watching each pointer update and child list integration step-by-step reveals how the algorithm maintains list integrity while flattening, which is hard to grasp from code alone.

no_opElement[0]: 1

Stack (top→bottom)

1

no_opElement[1]: 2

Stack (top→bottom)

2

1

peekElement[2]: 3

Stack (top→bottom)

3

2

1

no_opElement[2]: 3

Stack (top→bottom)

3

2

1

Contributes: "Tail found at node 10"

no_opElement[2]: 3

Stack (top→bottom)

3

2

1

Contributes: "Tail node 10 connected to node 4"

pushElement[2]: 3

Stack (top→bottom)

7

3

2

1

↑ pushed: 7

Contributes: "Child list spliced after node 3"

no_opElement[3]: 7

Stack (top→bottom)

7

3

2

1

peekElement[4]: 8

Stack (top→bottom)

8

7

3

2

1

no_opElement[4]: 8

Stack (top→bottom)

8

7

3

2

1

Contributes: "Tail found at node 12"

no_opElement[4]: 8

Stack (top→bottom)

8

7

3

2

1

Contributes: "Tail node 12 connected to node 9"

pushElement[4]: 8

Stack (top→bottom)

11

8

7

3

2

1

↑ pushed: 11

Contributes: "Nested child list spliced after node 8"

no_opElement[5]: 11

Stack (top→bottom)

11

8

7

3

2

1

no_opElement[6]: 12

Stack (top→bottom)

12

11

8

7

3

2

1

no_opElement[7]: 9

Stack (top→bottom)

9

12

11

8

7

3

2

1

no_opElement[8]: 10

Stack (top→bottom)

10

9

12

11

8

7

3

2

1

no_opElement[9]: 4

Stack (top→bottom)

4

10

9

12

11

8

7

3

2

1

no_opElement[10]: 5

Stack (top→bottom)

5

4

10

9

12

11

8

7

3

2

1

no_opElement[11]: 6

Stack (top→bottom)

6

5

4

10

9

12

11

8

7

3

2

1

no_op

Stack (top→bottom)

6

5

4

10

9

12

11

8

7

3

2

1

Contributes: "Flattened list head returned"

Key Takeaways

✓ Flattening is done in-place by splicing child lists directly into the main list without extra memory.

This insight is hard to see from code alone because pointer updates are subtle and interdependent.

✓ Finding the tail of the child list before splicing is crucial to reconnect the flattened list correctly.

Visualizing the tail traversal clarifies why this step is necessary to avoid losing nodes.

✓ Child pointers are removed immediately after splicing to prevent reprocessing and mark progress.

Seeing the child pointer cleared in the trace shows how the algorithm avoids infinite loops.