Remove Nth Node From End of List

▶

Steps

setup

Create dummy node pointing to head

A dummy node with value 0 is created and its next pointer is set to the head of the list. This simplifies edge cases such as removing the head node.

💡 Using a dummy node helps avoid special cases when the node to remove is the first node.

Line:

dummy = ListNode(0, head)

💡 The dummy node acts as a stable anchor before the actual list head.

traverse

Start recursion at dummy node

The recursive function 'recurse' is called with the dummy node as the current node to start traversal.

💡 Starting at dummy ensures the recursion covers the entire list including the node before head.

Line:

recurse(dummy)

💡 Recursion will move forward until it reaches the end of the list.

traverse

Recurse to next node (node 1)

The recursion moves forward by calling recurse on the next node (node with value 1).

💡 Each recursive call moves one step deeper into the list until the end is reached.

Line:

idx = recurse(node.next) + 1

💡 The recursion stack grows as we move forward, delaying processing until the end.

traverse

Recurse to next node (node 2)

Recursion continues by calling recurse on node with value 2.

💡 The recursion moves step-by-step towards the end of the list.

Line:

idx = recurse(node.next) + 1

💡 The recursion stack depth increases, preparing to count nodes from the end on return.

traverse

Recurse to next node (node 3)

Recursion moves forward to node with value 3.

💡 Each step moves closer to the end, where base case triggers.

Line:

idx = recurse(node.next) + 1

💡 The recursion stack is now deep enough to start counting nodes from the end on return.

traverse

Recurse to next node (node 4)

Recursion moves forward to node with value 4.

💡 Approaching the end of the list, preparing for base case.

Line:

idx = recurse(node.next) + 1

💡 The recursion stack is one step away from the end node.

traverse

Recurse to next node (node 5)

Recursion moves forward to the last node with value 5.

💡 The last node is reached; next recursion call will hit base case.

Line:

idx = recurse(node.next) + 1

💡 The recursion is at the deepest level, ready to start backtracking.

traverse

Base case reached: node is null

Recursion reaches the end of the list (null), returns 0 to start counting from the end.

💡 Base case triggers the backtracking process to count nodes from the end.

Line:

if not node:
    return 0

💡 Returning 0 signals the end of the list for counting purposes.

prune

Backtrack from node 5: index = 1

Returning from recursion at node 5, index is incremented to 1. Since index != n+1, no removal occurs.

💡 Counting nodes from the end starts here; index 1 means node 5 is the last node.

Line:

idx = recurse(node.next) + 1
if idx == self.n + 1:
    node.next = node.next.next

💡 Index counting helps identify the node before the one to remove.

prune

Backtrack from node 4: index = 2

Returning from recursion at node 4, index increments to 2. Still no removal since index != n+1.

💡 Node 4 is second from the end; counting continues.

Line:

idx = recurse(node.next) + 1
if idx == self.n + 1:
    node.next = node.next.next

💡 We are one step closer to the node before the one to remove.

prune

Backtrack from node 3: index = 3, remove node 4

At node 3, index increments to 3 which equals n+1. The next pointer of node 3 is updated to skip node 4, effectively removing it.

💡 When index equals n+1, the node after current is removed by pointer adjustment.

Line:

if idx == self.n + 1:
    node.next = node.next.next

💡 Pointer adjustment removes the target node without needing a previous pointer explicitly.

prune

Backtrack from node 2: index = 4

Returning from node 2, index increments to 4. No removal needed, recursion continues returning.

💡 Counting continues but removal already done.

Line:

return idx

💡 Backtracking continues to unwind recursion stack.

prune

Backtrack from node 1: index = 5

Returning from node 1, index increments to 5. No removal needed, recursion continues returning.

💡 Unwinding recursion stack back to dummy node.

Line:

return idx

💡 Backtracking completes with no further changes.

prune

Backtrack from dummy node: recursion ends

Returning from dummy node, recursion ends and the modified list head is returned.

💡 Returning dummy.next gives the new head of the updated list.

Line:

return dummy.next

💡 The dummy node allows returning the updated list head easily.

reconstruct

Final list after removal

The final linked list is returned starting from node 1, showing the list with node 4 removed.

💡 The list now correctly excludes the 2nd node from the end.

Line:

return dummy.next

💡 The algorithm successfully removed the target node by pointer adjustment during backtracking.

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

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        self.n = n
        def recurse(node):  # STEP 2-14
            if not node:  # STEP 8
                return 0
            idx = recurse(node.next) + 1  # STEP 3-7,9-13
            if idx == self.n + 1:  # STEP 11
                node.next = node.next.next  # STEP 11
            return idx
        dummy = ListNode(0, head)  # STEP 1
        recurse(dummy)  # STEP 2
        return dummy.next  # STEP 14-15

📊

Remove Nth Node From End of List - Watch the Algorithm Execute, Step by Step

Watching each recursive call and return helps you understand how recursion can simulate reverse traversal in a singly linked list, which is otherwise hard to visualize.

connect

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

advance

0

→

1

→

2

→

3

→

4

→

5

Result: 0

compare

0

→

1

→

2

→

3

→

4

→

5

Result: 1

compare

0

→

1

→

2

→

3

→

4

→

5

Result: 2

connect

0

→

1

→

2

→

3

→

4

→

5

Result: 3

advance

0

→

1

→

2

→

3

→

4

→

5

Result: 4

advance

0

→

1

→

2

→

3

→

4

→

5

Result: 5

advance

0

→

1

→

2

→

3

→

4

→

5

reconstruct

1

→

2

→

3

→

5

Result: [1, 2, 3, 5]

Key Takeaways

✓ Recursion can simulate reverse traversal in a singly linked list by backtracking from the end.

This is hard to see from code alone because recursion hides the call stack and the order of execution.

✓ Using a dummy node simplifies edge cases and pointer adjustments when removing nodes.

Visualizing the dummy node clarifies why it is used and how it anchors the list.

✓ The node removal happens by adjusting the 'next' pointer of the node before the target during backtracking.

Seeing the pointer change in the visualization makes it clear how the node is removed without explicit previous pointers.

Practice

1. You are given a circular array where each element represents the number of steps to move forward or backward. The goal is to determine if there exists a cycle where all moves are in the same direction and the cycle length is greater than 1. Which algorithmic approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Fast and slow pointer technique (Floyd's cycle detection) adapted for circular arrays with direction checks

B. Greedy approach that tries to jump as far as possible each time without revisiting indices

C. Dynamic programming to store reachable indices and cycle lengths

D. Brute force simulation with a visited set for each start index

Solution

1. Step 1: Understand problem constraints

   The problem requires detecting cycles in a circular array with direction consistency and cycle length > 1.

2. Step 2: Identify algorithm that efficiently detects cycles

   Fast and slow pointer (Floyd's cycle detection) can detect cycles in O(n) time and O(1) space, with added direction checks to ensure cycle validity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Fast-slow pointer is classic for cycle detection in sequences [OK]

Hint: Cycle detection in sequences -> fast-slow pointer [OK]

Common Mistakes:

• Thinking greedy jumps detect cycles correctly
• Assuming DP applies here
• Using brute force is optimal

2. Consider the following Python code implementing Floyd's cycle detection and cycle start finding algorithm. Given the linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle starts at node with value 2), what value does the function return?

easy

A. 4

B. 3

C. 2

D. None

Solution

1. Step 1: Trace slow and fast pointers until they meet

   Slow moves 1 step, fast moves 2 steps. They meet inside the cycle at node with value 3 or 4 after some iterations.

2. Step 2: Reset one pointer to head and move both one step at a time

   Both pointers meet at node with value 2, which is the cycle start.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle start node value is 2 as per algorithm [OK]

Hint: Cycle start found by meeting pointers after reset [OK]

Common Mistakes:

• Returning meeting point instead of cycle start
• Off-by-one error in pointer movement
• Returning None incorrectly

3. Given the following Python code for reorderList and the input list 1->2->3->4, what is the value of the node pointed to by left after the first merge step in the recursion unwinding?

easy

A. Node with value 3

B. Node with value 2

C. Node with value 4

D. Node with value 1

Solution

1. Step 1: Trace recursion to the end

   Recursion reaches right = None, then unwinds from node 4 back to node 1.

2. Step 2: First merge step during unwinding

   At right=4, left=1, tmp=left.next=2; left.next=4; 4.next=2; left=2 after merge.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   After first merge, left points to node with value 2 [OK]

Hint: left moves forward after merging right node [OK]

Common Mistakes:

• Confusing left pointer update
• Off-by-one in recursion unwind
• Misreading next pointer assignments

4. What is the space complexity of the optimal palindrome linked list check that reverses the second half in-place?

medium

A. O(n) due to storing node values in an array

B. O(1) because reversal is done in-place without extra data structures

C. O(log n) due to recursion stack in reversal

D. O(n) due to recursion stack in reversal

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm reverses the second half in-place using pointers, no extra arrays or stacks.

2. Step 2: Check for recursion stack

   The reversal is iterative, so no recursion stack space is used.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   In-place iterative reversal uses constant extra space [OK]

Hint: Iterative reversal uses O(1) space, recursion would add stack space [OK]

Common Mistakes:

• Confusing iterative reversal with recursive reversal
• Assuming array storage is needed for palindrome check
• Forgetting recursion stack space in complexity

5. Suppose you want to find the middle node of a linked list, but the list is circular (the last node points back to the head). Which modification to the two-pointer approach correctly finds the middle node without infinite looping?

hard

A. Use the same two-pointer approach but add a visited set to detect cycles and stop when fast pointer revisits a node.

B. Use recursion to count nodes until the head is reached again, then find middle by index.

C. Convert the circular list to a linear list by breaking the cycle first, then apply the standard two-pointer approach.

D. Modify the loop to stop when fast or fast.next equals the head node, then return slow pointer.

Solution

1. Step 1: Understand circular list behavior

   In a circular list, fast pointer will loop infinitely unless we detect when it cycles back to head.

2. Step 2: Modify loop condition

   Stop when fast or fast.next equals head to avoid infinite loop; slow pointer will be at middle.

3. Step 3: Compare alternatives

   Visited set adds extra space; breaking cycle modifies input; recursion risks stack overflow.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stopping at head detects cycle end without extra space [OK]

Hint: Detect cycle by checking if fast pointer returns to head [OK]

Common Mistakes:

• Using visited set wastes space
• Breaking cycle modifies input
• Recursion risks stack overflow