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.

Practice

1. Consider the following Python code implementing browser history with two stacks. After executing the sequence of operations below, what is the output of the last back call?

browserHistory = BrowserHistory("leetcode.com")
browserHistory.visit("google.com")
browserHistory.visit("facebook.com")
browserHistory.visit("youtube.com")
print(browserHistory.back(1))
print(browserHistory.back(1))
print(browserHistory.forward(1))

easy

A. "youtube.com"

B. "google.com"

C. "facebook.com"

D. "leetcode.com"

Solution

1. Step 1: Trace back(1) after visiting youtube.com

   back_stack = ["leetcode.com", "google.com", "facebook.com", "youtube.com"] Pop "youtube.com" to forward_stack, back_stack top is "facebook.com".

2. Step 2: Trace back(1) again and forward(1)

   Second back(1): pop "facebook.com" to forward_stack, top is "google.com". Forward(1): pop "facebook.com" from forward_stack back to back_stack, top is "facebook.com".

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Last forward returns "facebook.com" as expected [OK]

Hint: Back and forward operations move URLs between stacks correctly [OK]

Common Mistakes:

• Off-by-one errors in popping stacks
• Confusing forward and back stacks
• Returning wrong top element after operations

2. You need to implement a data structure that supports the following operations efficiently: get element by index, add element at head, add element at tail, add element at an arbitrary index, and delete element at an arbitrary index. Which approach best guarantees efficient average-case performance for all these operations?

easy

A. Use a dynamic array and resize it when needed to support all operations.

B. Use a balanced binary search tree keyed by index to support all operations in O(log n).

C. Use a singly linked list with sentinel head and tail pointers, maintaining the size for boundary checks.

D. Use a hash map to store index-to-node mappings for constant time access.

Solution

1. Step 1: Understand operation requirements

   The problem requires efficient get, add at head, add at tail, add at index, and delete at index operations.

2. Step 2: Evaluate approaches

   Dynamic arrays have O(n) add/delete at head or arbitrary index due to shifting. Singly linked lists have O(1) add at head/tail but O(n) get and add/delete at arbitrary index. Balanced BSTs keyed by index can support all operations in O(log n) time, providing efficient average-case performance. Hash maps do not maintain order and cannot efficiently support index-based operations.

3. Step 3: Choose best approach

   Balanced BST keyed by index offers O(log n) for all operations, which is more efficient on average than linked list or array for arbitrary index operations.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Balanced BST supports all required operations efficiently [OK]

Hint: Balanced BST keyed by index supports all operations in O(log n) [OK]

Common Mistakes:

• Assuming linked list provides efficient arbitrary index access
• Thinking arrays support O(1) insertions at head
• Assuming hash maps maintain order

3. Given the following code for partitioning a linked list around value x = 3, and the input list: 1 -> 4 -> 2 -> 5, what is the final reordered list returned by the function?

easy

A. 1 -> 4 -> 2 -> 5

B. 1 -> 2 -> 4 -> 5

C. 2 -> 1 -> 4 -> 5

D. 4 -> 1 -> 2 -> 5

Solution

1. Step 1: Trace initial pointers with input 1 -> 4 -> 2 -> 5 and x=3

   Start with dummy -> 1 -> 4 -> 2 -> 5, less_tail and prev at dummy, current at 1.

2. Step 2: Process nodes

   Node 1 < 3, less_tail.next == current, move less_tail and prev forward. Node 4 >= 3, move prev and current forward. Node 2 < 3, less_tail.next != current, so remove 2 and insert after less_tail. Final list: 1 -> 2 -> 4 -> 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Nodes less than 3 appear first in original order, then others [OK]

Hint: Track less_tail and prev carefully to avoid skipping nodes [OK]

Common Mistakes:

• Swapping values instead of nodes
• Incorrect pointer updates causing lost nodes
• Assuming order changes within partitions

4. Examine the following buggy code snippet from an optimal linked list implementation. Which line contains the subtle bug that can cause the tail pointer to point to a deleted node after a deletion at the tail?

medium

A. Line 8: self.tail = prev

B. Line 6: prev.next = prev.next.next

C. Line 3: if index < 0 or index >= self.size:

D. Line 7: if index == self.size - 1:

Solution

1. Step 1: Understand tail update condition

   The tail pointer should update when deleting the last node, which is at index size-1 before deletion.

2. Step 2: Identify bug

   At line 8, the tail pointer is set to prev, but prev may not be the correct new tail if the deleted node was the last node. The tail pointer should be updated after size decrement and possibly set to the correct node.

3. Step 3: Correct fix

   Update tail pointer after size decrement and ensure it points to the last node in the list.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tail pointer update must correctly reflect the new last node after deletion [OK]

Hint: Tail pointer update must be done carefully after deletion [OK]

Common Mistakes:

• Updating tail before size decrement
• Not updating tail on last node deletion
• Incorrect traversal to prev node

5. Suppose the problem is modified so that nodes can be reused multiple times (i.e., after reversing a group, nodes can appear again in subsequent groups). Which of the following changes to the algorithm correctly handles this scenario?

hard

A. Modify the algorithm to create new nodes for each group reversal to avoid modifying original nodes in place.

B. This problem cannot be solved by reversal; instead, use a queue to simulate repeated node usage.

C. Use recursion with memoization to store reversed groups and reuse them without modifying the original list.

D. Use the same iterative reversal approach but reset pointers to allow reusing nodes in multiple groups.

Solution

1. Step 1: Understand node reuse implication

   Reusing nodes means original nodes must remain unchanged or duplicated to appear multiple times.

2. Step 2: Evaluate algorithm modifications

   In-place reversal modifies nodes destructively, so creating new nodes for each group is necessary to preserve original nodes.

3. Step 3: Assess other options

   Resetting pointers (A) breaks list integrity; recursion with memoization (C) is complex and not standard; queue simulation (B) does not solve reversal reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Duplicating nodes preserves original list for reuse [OK]

Hint: Node reuse requires duplication, not in-place reversal [OK]

Common Mistakes:

• Trying to reuse nodes in place
• Ignoring list integrity
• Assuming recursion memoization solves reuse