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. Consider the following Python code implementing the optimized fast-slow pointer approach for detecting a cycle in a circular array. Given the input nums = [2, -1, 1, 2, 2], what is the return value of the function circularArrayLoop(nums)?

easy

A. Raises an IndexError

B. false

C. true

D. Infinite loop

Solution

1. Step 1: Trace first iteration with i=0

   Start at index 0, direction is positive. Moves: 0->2->3->0 forms a cycle of length >1 with consistent direction.

2. Step 2: Detect cycle and return true

   Fast and slow pointers meet at index 0, cycle length >1, so function returns true.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detected correctly for input [2, -1, 1, 2, 2] [OK]

Hint: Trace fast and slow pointers until they meet [OK]

Common Mistakes:

• Confusing direction checks
• Missing cycle length 1 check
• Miscomputing next index modulo

2. Given the following code snippet, what is the output when calling findDuplicate([3,1,3,4,2])?

easy

A. 3

B. 1

C. 4

D. 2

Solution

1. Step 1: Trace first phase to find intersection point

   Initialize slow=3, fast=3 (nums[0]=3). Iteration 1: slow=nums[3]=4, fast=nums[nums[3]]=nums[4]=2. Iteration 2: slow=nums[4]=2, fast=nums[nums[2]]=nums[3]=4. Iteration 3: slow=nums[2]=3, fast=nums[nums[4]]=nums[2]=3. They meet at 3.

2. Step 2: Trace second phase to find cycle entrance

   Reset slow=nums[0]=3. Since slow==fast==3, loop ends immediately. Return 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detection returns duplicate 3 correctly [OK]

Hint: Cycle detection returns the duplicate value where pointers meet [OK]

Common Mistakes:

• Confusing slow and fast pointer updates
• Off-by-one errors in indexing
• Returning the wrong pointer value

3. Given the following code for checking if a linked list is a palindrome, what is the final return value when the input list is 1 -> 2 -> 1?

easy

A. Infinite loop

B. False

C. True

D. Raises an exception due to null pointer

Solution

1. Step 1: Trace fast and slow pointers

   For list 1 -> 2 -> 1, slow ends at node with value 2, fast reaches end.

2. Step 2: Reverse second half and compare

   Second half starting at 2 -> 1 is reversed to 1 -> 2. Compare nodes: 1==1, 2==2, all match, so return True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Palindrome list returns True after correct reversal and comparison [OK]

Hint: Check pointer movement and reversed half comparison carefully [OK]

Common Mistakes:

• Misplacing slow pointer causing wrong half reversal
• Off-by-one error in comparison loop
• Forgetting to advance second_half_start pointer

4. Examine the following code snippet intended to detect the start of a cycle in a linked list. Identify the line containing the subtle bug that can cause a runtime error or infinite loop.

medium

A. Line 5: fast = fast.next.next

B. Line 3: while fast:

C. Line 7: if slow == fast:

D. Line 11: while ptr1 != ptr2:

Solution

1. Step 1: Check loop condition safety

   The loop condition only checks if fast is not None, but fast.next may be None, so fast.next.next can cause an exception.

2. Step 2: Identify fix

   The loop condition should check both fast and fast.next to avoid null pointer exceptions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Accessing fast.next.next without checking fast.next causes runtime error [OK]

Hint: Always check fast and fast.next before accessing fast.next.next [OK]

Common Mistakes:

• Missing fast.next check
• Returning meeting point as cycle start
• Infinite loop due to wrong loop condition

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