Flatten a Multilevel Doubly Linked List

🎯

Flatten a Multilevel Doubly Linked List

mediumDESIGNAmazonMicrosoftGoogle

Imagine you have a complex file system where folders can contain files and other folders nested arbitrarily deep. You want to list all files in a single linear order, flattening the hierarchy.

💡 This problem involves traversing and modifying a complex linked data structure with multiple levels. Beginners often struggle because it requires careful pointer manipulation and understanding how to traverse nested structures without losing track of nodes.

📋

Problem Statement

You are given a doubly linked list where in addition to the next and previous pointers, each node may have a child pointer, which may 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. Flatten the list so that all the nodes appear in a single-level, doubly linked list. The nodes should appear in the order they are encountered in a depth-first traversal.

1 ≤ Number of nodes ≤ 10^5Node values are integersChild pointers may be nullThe list may be empty (head is null)

💡

Example

Input"1---2---3---4---5---6--NULL\n |\n 7---8---9---10--NULL\n |\n 11--12--NULL"

Output1---2---3---7---8---11---12---9---10---4---5---6--NULL

Starting at head 1, traverse next nodes until 3, then go down child list starting at 7, flattening recursively, then continue with 4, 5, 6.

• Empty list (head is null) → output is null
• List with no child pointers → output is the same list
• List where every node has a child → output is a deeply nested flattened list
• List with multiple levels of nesting → output is a single-level list preserving DFS order

⚠️

Common Mistakes

Not removing the child pointer after splicing

Leads to infinite loops or incorrect list structure

✅ Set node.child = None/null after splicing child list

Incorrectly updating prev pointers when splicing

Broken doubly linked list, causing traversal errors

✅ Always update both next and prev pointers when connecting nodes

Using recursion without considering stack overflow

Runtime error on very deep nested lists

✅ Use iterative approach with explicit stack for deep nesting

Finding tail of child list repeatedly in in-place approach

Leads to O(n^2) time complexity and slow performance

✅ Use stack-based approach or memoize tail nodes if possible

Not handling empty list input

Null pointer exceptions or crashes

✅ Check if head is null at start and return immediately

🧠

Brute Force (Pure Recursion)

💡 Starting with a pure recursive approach helps understand the problem's depth-first nature and how child lists are integrated. It is intuitive but can cause stack overflow on deep nesting.

Intuition

Recursively flatten each child list and splice it into the main list at the node with the child pointer, then continue flattening the rest of the list.

Algorithm

1. If the current node is null, return null.
2. Recursively flatten the child list if it exists.
3. Splice the flattened child list between the current node and the next node.
4. Recursively flatten the next node after splicing and return the head.

💡 The challenge is to correctly connect the child list in place without losing track of the next nodes, which recursion helps manage by implicit call stack.

</>

Code

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):
    if not head:
        return head

    def dfs(node):
        curr = node
        last = node
        while curr:
            next_node = curr.next
            if curr.child:
                child_last = dfs(curr.child)
                curr.next = curr.child
                curr.child.prev = curr
                curr.child = None
                if next_node:
                    child_last.next = next_node
                    next_node.prev = child_last
                last = child_last
            else:
                last = curr
            curr = next_node
        return last

    dfs(head)
    return head

# Driver code to test
if __name__ == '__main__':
    # Build example list manually or use helper functions
    pass  # For brevity, driver omitted

Line Notes

if not head:Handle empty list edge case immediately

def dfs(node):Define recursive helper to flatten starting at node

while curr:Traverse current level nodes sequentially

if curr.child:When child exists, recursively flatten child list

curr.next = curr.childSplice child list into next pointer

curr.child.prev = currMaintain doubly linked property backward

curr.child = NoneRemove child pointer after splicing

if next_node:Reconnect the tail of child list to next node

return lastReturn last node of flattened list for linking

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node(int val) {
        this.val = val;
    }
}

public class Solution {
    public Node flatten(Node head) {
        if (head == null) return head;
        dfs(head);
        return head;
    }

    private Node dfs(Node node) {
        Node curr = node;
        Node last = node;
        while (curr != null) {
            Node next = curr.next;
            if (curr.child != null) {
                Node childLast = dfs(curr.child);
                curr.next = curr.child;
                curr.child.prev = curr;
                curr.child = null;
                if (next != null) {
                    childLast.next = next;
                    next.prev = childLast;
                }
                last = childLast;
            } else {
                last = curr;
            }
            curr = next;
        }
        return last;
    }

    // Main method omitted for brevity
}

Line Notes

if (head == null) return head;Quickly handle empty input

private Node dfs(Node node) {Recursive helper to flatten from node

while (curr != null) {Iterate current level nodes

if (curr.child != null) {Process child list recursively

curr.next = curr.child;Splice child list into main list

curr.child.prev = curr;Maintain backward link

curr.child = null;Remove child pointer after splicing

if (next != null) {Reconnect tail of child list to next node

return last;Return last node for linking

class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
    Node(int _val) : val(_val), prev(nullptr), next(nullptr), child(nullptr) {}
};

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return head;
        dfs(head);
        return head;
    }

private:
    Node* dfs(Node* node) {
        Node* curr = node;
        Node* last = node;
        while (curr) {
            Node* next = curr->next;
            if (curr->child) {
                Node* childLast = dfs(curr->child);
                curr->next = curr->child;
                curr->child->prev = curr;
                curr->child = nullptr;
                if (next) {
                    childLast->next = next;
                    next->prev = childLast;
                }
                last = childLast;
            } else {
                last = curr;
            }
            curr = next;
        }
        return last;
    }
};

// main() omitted for brevity

Line Notes

if (!head) return head;Handle empty list edge case

Node* dfs(Node* node) {Recursive helper to flatten starting at node

while (curr) {Traverse nodes at current level

if (curr->child) {Recursively flatten child list

curr->next = curr->child;Splice child list into next pointer

curr->child->prev = curr;Maintain backward link

curr->child = nullptr;Remove child pointer after splicing

if (next) {Reconnect tail of child list to next node

return last;Return last node of flattened list

class Node {
    constructor(val, prev = null, next = null, child = null) {
        this.val = val;
        this.prev = prev;
        this.next = next;
        this.child = child;
    }
}

var flatten = function(head) {
    if (!head) return head;

    function dfs(node) {
        let curr = node;
        let last = node;
        while (curr) {
            let next = curr.next;
            if (curr.child) {
                let childLast = dfs(curr.child);
                curr.next = curr.child;
                curr.child.prev = curr;
                curr.child = null;
                if (next) {
                    childLast.next = next;
                    next.prev = childLast;
                }
                last = childLast;
            } else {
                last = curr;
            }
            curr = next;
        }
        return last;
    }

    dfs(head);
    return head;
};

// Example usage omitted for brevity

Line Notes

if (!head) return head;Return immediately if list is empty

function dfs(node) {Recursive helper to flatten from node

while (curr) {Traverse current level nodes

if (curr.child) {Process child list recursively

curr.next = curr.child;Splice child list into main list

curr.child.prev = curr;Maintain backward link

curr.child = null;Remove child pointer after splicing

if (next) {Reconnect tail of child list to next node

return last;Return last node for linking

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack in worst case

Each node is visited once, but recursion depth can be up to n in worst case of deep nesting.

💡 For n=1000 nodes, this means roughly 1000 operations but recursion stack could be large if nesting is deep.

Interview Verdict: Accepted but may cause stack overflow on very deep nesting

This approach is intuitive and acceptable for moderate input sizes but risky for very deep lists due to recursion depth limits.

🧠

Iterative DFS Using Stack

💡 Using an explicit stack to simulate recursion avoids stack overflow and clarifies the depth-first traversal order, making it more robust for large inputs.

Intuition

Traverse the list iteratively, pushing next nodes onto a stack before diving into child lists, so you can return to the next nodes after finishing children.

Algorithm

1. Initialize a stack and push the head node.
2. Pop a node from the stack and process it, connecting it to the previous node.
3. If the node has a next pointer, push it onto the stack.
4. If the node has a child pointer, push the child onto the stack and remove the child pointer.
5. Repeat until the stack is empty.

💡 The stack keeps track of nodes to visit next, ensuring depth-first order without recursion.

</>

Code

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):
    if not head:
        return head

    stack = [head]
    prev = None

    while stack:
        curr = stack.pop()
        if prev:
            prev.next = curr
            curr.prev = prev
        if curr.next:
            stack.append(curr.next)
        if curr.child:
            stack.append(curr.child)
            curr.child = None
        prev = curr

    return head

# Driver code omitted for brevity

Line Notes

if not head:Handle empty list edge case

stack = [head]Initialize stack with head node to start traversal

while stack:Process nodes until none left

curr = stack.pop()Pop node to process in DFS order

if prev:Link current node with previous node

if curr.next:Push next node to stack to visit later

if curr.child:Push child node to stack to visit next

curr.child = NoneRemove child pointer after pushing

prev = currUpdate previous pointer

import java.util.Stack;

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node(int val) {
        this.val = val;
    }
}

public class Solution {
    public Node flatten(Node head) {
        if (head == null) return head;

        Stack<Node> stack = new Stack<>();
        stack.push(head);
        Node prev = null;

        while (!stack.isEmpty()) {
            Node curr = stack.pop();
            if (prev != null) {
                prev.next = curr;
                curr.prev = prev;
            }
            if (curr.next != null) {
                stack.push(curr.next);
            }
            if (curr.child != null) {
                stack.push(curr.child);
                curr.child = null;
            }
            prev = curr;
        }

        return head;
    }

    // Main method omitted for brevity
}

Line Notes

if (head == null) return head;Handle empty input quickly

Stack<Node> stack = new Stack<>();Use stack to simulate recursion

stack.push(head);Start traversal from head

while (!stack.isEmpty()) {Process nodes until stack empty

Node curr = stack.pop();Pop node to process

if (prev != null) {Link current node with previous

if (curr.next != null) {Push next node for later processing

if (curr.child != null) {Push child node to process next

curr.child = null;Remove child pointer after pushing

prev = curr;Update previous pointer

#include <stack>

class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
    Node(int _val) : val(_val), prev(nullptr), next(nullptr), child(nullptr) {}
};

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return head;

        std::stack<Node*> stack;
        stack.push(head);
        Node* prev = nullptr;

        while (!stack.empty()) {
            Node* curr = stack.top();
            stack.pop();
            if (prev) {
                prev->next = curr;
                curr->prev = prev;
            }
            if (curr->next) {
                stack.push(curr->next);
            }
            if (curr->child) {
                stack.push(curr->child);
                curr->child = nullptr;
            }
            prev = curr;
        }

        return head;
    }
};

// main() omitted for brevity

Line Notes

if (!head) return head;Handle empty list edge case

std::stack<Node*> stack;Stack to simulate recursion

stack.push(head);Start from head node

while (!stack.empty()) {Process nodes until stack empty

Node* curr = stack.top();Pop node to process

if (prev) {Link current node with previous

if (curr->next) {Push next node for later processing

if (curr->child) {Push child node to process next

curr->child = nullptr;Remove child pointer after pushing

prev = curr;Update previous pointer

class Node {
    constructor(val, prev = null, next = null, child = null) {
        this.val = val;
        this.prev = prev;
        this.next = next;
        this.child = child;
    }
}

var flatten = function(head) {
    if (!head) return head;

    const stack = [head];
    let prev = null;

    while (stack.length > 0) {
        const curr = stack.pop();
        if (prev) {
            prev.next = curr;
            curr.prev = prev;
        }
        if (curr.next) {
            stack.push(curr.next);
        }
        if (curr.child) {
            stack.push(curr.child);
            curr.child = null;
        }
        prev = curr;
    }

    return head;
};

// Example usage omitted for brevity

Line Notes

if (!head) return head;Return immediately if list is empty

const stack = [head];Initialize stack with head node

while (stack.length > 0) {Process nodes until stack empty

const curr = stack.pop();Pop node to process in DFS order

if (prev) {Link current node with previous

if (curr.next) {Push next node for later processing

if (curr.child) {Push child node to process next

curr.child = null;Remove child pointer after pushing

prev = curr;Update previous pointer

⏱

Complexity

TimeO(n)

SpaceO(n) due to explicit stack in worst case

Each node is visited once; stack size can grow up to n in worst case of deep nesting.

💡 For n=1000 nodes, this means about 1000 operations and stack size up to 1000 in worst case.

Interview Verdict: Accepted and more robust than recursion for deep nesting

This approach avoids recursion limits and is preferred in interviews for large inputs.

🧠

In-Place Iterative Flattening Without Extra Stack

💡 This approach uses pointer manipulation to flatten the list in place by iterating and splicing child lists directly, saving space by not using an explicit stack.

Intuition

Iterate through the list; when a child is found, splice the entire child list between current node and next node, then continue iteration.

Algorithm

1. Start from head and iterate through the list.
2. When a node with a child is found, find the tail of the child list.
3. Connect the tail's next pointer to the current node's next node if it exists.
4. Splice the child list between current node and next node, update pointers accordingly.
5. Remove the child pointer and continue iteration from the current node's next.

💡 The key is carefully updating pointers to maintain list integrity while flattening in place.

</>

Code

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
    while curr:
        if curr.child:
            child = curr.child
            # Find tail of child list
            tail = child
            while tail.next:
                tail = tail.next
            # Connect tail to curr.next
            if curr.next:
                tail.next = curr.next
                curr.next.prev = tail
            # Connect curr to child
            curr.next = child
            child.prev = curr
            curr.child = None
        curr = curr.next
    return head

# Driver code omitted for brevity

Line Notes

curr = headStart iteration from head

while curr:Traverse the list sequentially

if curr.child:Process child list when found

tail = childFind tail of child list to connect next nodes

while tail.next:Traverse to end of child list

if curr.next:Connect tail to next node if exists

curr.next = childSplice child list after current node

child.prev = currMaintain backward link

curr.child = NoneRemove child pointer after splicing

curr = curr.nextMove to next node

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node(int val) {
        this.val = val;
    }
}

public class Solution {
    public Node flatten(Node head) {
        Node curr = head;
        while (curr != null) {
            if (curr.child != null) {
                Node child = curr.child;
                Node tail = child;
                while (tail.next != null) {
                    tail = tail.next;
                }
                if (curr.next != null) {
                    tail.next = curr.next;
                    curr.next.prev = tail;
                }
                curr.next = child;
                child.prev = curr;
                curr.child = null;
            }
            curr = curr.next;
        }
        return head;
    }

    // Main method omitted for brevity
}

Line Notes

Node curr = head;Initialize current pointer at head

while (curr != null) {Iterate through list nodes

if (curr.child != null) {Process child list when found

Node tail = child;Find tail of child list

while (tail.next != null) {Traverse to end of child list

if (curr.next != null) {Connect tail to next node if exists

curr.next = child;Splice child list after current node

child.prev = curr;Maintain backward link

curr.child = null;Remove child pointer after splicing

curr = curr.next;Move to next node

class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
    Node(int _val) : val(_val), prev(nullptr), next(nullptr), child(nullptr) {}
};

class Solution {
public:
    Node* flatten(Node* head) {
        Node* curr = head;
        while (curr) {
            if (curr->child) {
                Node* child = curr->child;
                Node* tail = child;
                while (tail->next) {
                    tail = tail->next;
                }
                if (curr->next) {
                    tail->next = curr->next;
                    curr->next->prev = tail;
                }
                curr->next = child;
                child->prev = curr;
                curr->child = nullptr;
            }
            curr = curr->next;
        }
        return head;
    }
};

// main() omitted for brevity

Line Notes

Node* curr = head;Start iteration from head

while (curr) {Traverse list nodes

if (curr->child) {Process child list when found

Node* tail = child;Find tail of child list

while (tail->next) {Traverse to end of child list

if (curr->next) {Connect tail to next node if exists

curr->next = child;Splice child list after current node

child->prev = curr;Maintain backward link

curr->child = nullptr;Remove child pointer after splicing

curr = curr->next;Move to next node

class Node {
    constructor(val, prev = null, next = null, child = null) {
        this.val = val;
        this.prev = prev;
        this.next = next;
        this.child = child;
    }
}

var flatten = function(head) {
    let curr = head;
    while (curr) {
        if (curr.child) {
            let child = curr.child;
            let tail = child;
            while (tail.next) {
                tail = tail.next;
            }
            if (curr.next) {
                tail.next = curr.next;
                curr.next.prev = tail;
            }
            curr.next = child;
            child.prev = curr;
            curr.child = null;
        }
        curr = curr.next;
    }
    return head;
};

// Example usage omitted for brevity

Line Notes

let curr = head;Initialize current pointer at head

while (curr) {Iterate through list nodes

if (curr.child) {Process child list when found

let tail = child;Find tail of child list

while (tail.next) {Traverse to end of child list

if (curr.next) {Connect tail to next node if exists

curr.next = child;Splice child list after current node

child.prev = curr;Maintain backward link

curr.child = null;Remove child pointer after splicing

curr = curr.next;Move to next node

⏱

Complexity

TimeO(n^2) in worst case

SpaceO(1) extra space

Finding tail of child list can take O(k) time repeatedly, leading to O(n^2) in worst case of many small child lists.

💡 For n=1000 nodes with many children, this approach may do up to 1,000,000 operations due to repeated tail searches.

Interview Verdict: Accepted but inefficient for large inputs with many children

This approach saves space but can be slow due to repeated tail traversals; better for small or shallow lists.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the iterative DFS with stack approach balances clarity, robustness, and efficiency, making it the best choice to code.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Pure Recursion)	O(n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code due to stack overflow risk
2. Iterative DFS Using Stack	O(n)	O(n) explicit stack	No	N/A	Preferred approach to code in interviews
3. In-Place Iterative Flattening Without Extra Stack	O(n^2) worst case	O(1)	No	N/A	Good to mention, but avoid coding due to inefficiency

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach, followed by iterative improvements. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force recursive approach and its limitations.Step 3: Explain the iterative DFS approach using a stack to avoid recursion limits.Step 4: Discuss the in-place iterative approach and tradeoffs.Step 5: Code the preferred approach and test with edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of linked list pointer manipulation, recursion vs iteration, handling nested structures, and ability to optimize space/time tradeoffs.

Common Follow-ups

• How would you handle very deep nesting without recursion? → Use iterative DFS with stack.
• Can you flatten the list in place without extra space? → Yes, but watch for tail traversal cost.

💡 These follow-ups check your ability to optimize recursion and space usage, common interview extensions.

🔍

Pattern Recognition

When to Use

1) When a linked list has nested child pointers, 2) When flattening requires depth-first traversal, 3) When pointer manipulation is needed, 4) When recursion or stack can be used to manage nested structures.

Signature Phrases

multilevel doubly linked listflatten the listchild pointerdepth-first traversal

NOT This Pattern When

This is not a simple linked list traversal or sorting problem; it requires handling nested pointers and flattening.

Similar Problems

Flatten Binary Tree to Linked List - similar flattening of nested structuresFlatten Nested List Iterator - similar depth-first flattening of nested lists

Practice

1. Given the following code for odd-even linked list rearrangement, what is the output list after running the function on the input list [1, 2, 3, 4]?

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    odd.next = even_head
    return head

# Input list: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = oddEvenList(head)
curr = new_head
res = []
while curr:
    res.append(curr.val)
    curr = curr.next
print(res)

easy

A. [1, 2, 3, 4]

B. [1, 3, 2, 4]

C. [2, 4, 1, 3]

D. [1, 3, 4, 2]

Solution

1. Step 1: Trace first iteration of while loop

   odd=1, even=2, even.next=3; odd.next=3, odd moves to 3; even.next=4, even moves to 4.

2. Step 2: Loop ends as even.next is null; link odd.next to even_head (2)

   Final list order: 1 -> 3 -> 2 -> 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected odd-even rearrangement for input [1,2,3,4] [OK]

Hint: Odd nodes first, then even nodes in original order [OK]

Common Mistakes:

• Confusing node values with indices
• Off-by-one errors in pointer updates

2. You are given a singly linked list and need to reorder it so that the nodes are arranged in the sequence: first node, last node, second node, second last node, and so on. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Store all nodes in an array, then reorder by reassigning next pointers using two pointers from ends.

B. Use a greedy approach by alternating nodes from the start and end without modifying the list structure.

C. Use dynamic programming to store intermediate reorder states and build the final list.

D. Find the middle of the list, reverse the second half, then merge the two halves alternately.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reordering nodes in a specific pattern without extra space overhead.

2. Step 2: Evaluate approaches for time and space

   Finding the middle, reversing the second half, and merging achieves O(n) time and O(1) space, unlike storing nodes or DP which use extra space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal approach uses middle finding and reversing [OK]

Hint: Middle + reverse + merge is classic reorder pattern [OK]

Common Mistakes:

• Thinking greedy pointer swaps suffice
• Using extra arrays unnecessarily
• Confusing DP with linked list reorder

3. What is the time complexity of the recursive approach that converts a binary number in a linked list to an integer by accumulating the value with bit shifts?

medium

A. O(n log n) due to bit shifts at each node

B. O(n^2) because recursion stack causes repeated computations

C. O(n) because each node is visited once with constant work

D. O(n) time but O(n^2) space due to recursion stack

Solution

1. Step 1: Analyze time per node

   Each node is processed once, performing a constant number of bit operations (shift and OR).

2. Step 2: Consider recursion overhead

   Recursion depth is n, but no repeated computations occur; each call does O(1) work.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal with constant work per node [OK]

Hint: Bit shifts are O(1) operations, not O(log n) [OK]

Common Mistakes:

• Assuming bit shifts cost O(log n)
• Confusing recursion stack space with time complexity
• Thinking recursion causes repeated work

4. The following code attempts to implement the two stacks browser history. Identify the line containing the subtle bug that causes forward navigation to return outdated pages after visiting a new URL.

class BrowserHistory:
    def __init__(self, homepage: str):
        self.back_stack = [homepage]
        self.forward_stack = []

    def visit(self, url: str) -> None:
        self.back_stack.append(url)
        # Missing forward_stack.clear() here

    def back(self, steps: int) -> str:
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]

medium

A. Line where back_stack.append(url) is called in visit

B. Line where forward_stack.clear() should be called but is missing in visit

C. Line where back_stack.pop() is called in back method

D. Line where forward_stack.pop() is called in forward method

Solution

1. Step 1: Identify visit method behavior

   Visit appends new URL but does not clear forward_stack, so forward history remains outdated.

2. Step 2: Understand impact on forward navigation

   Without clearing forward_stack, forward() returns stale pages that should have been discarded.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Clearing forward_stack on visit is essential to maintain correct forward history [OK]

Hint: Visit must clear forward history to avoid stale pages [OK]

Common Mistakes:

• Forgetting to clear forward stack on visit
• Incorrectly popping from back stack
• Mismanaging stack boundaries

5. What is the time complexity of the optimal iterative approach that reverses a linked list in groups of k nodes, and why?

medium

A. O(nk), because each group reversal takes O(k) and there are n/k groups.

B. O(n), because each node is visited and reversed exactly once.

C. O(n log k), because reversing each group involves log k steps due to pointer updates.

D. O(n + k), because the algorithm traverses the list plus reverses k nodes.

Solution

1. Step 1: Analyze group reversal cost

   Each group of k nodes is reversed in O(k) time.

2. Step 2: Count total groups and total nodes processed

   There are approximately n/k groups, so total time is O(k * n/k) = O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each node is processed once during reversal [OK]

Hint: Total nodes processed once -> O(n) time [OK]

Common Mistakes:

• Multiplying n by k incorrectly
• Assuming log k factor in reversal
• Ignoring that groups partition the list