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. Given the following Python code implementing the optimal recursive addition of two linked lists representing numbers in forward order, what is the value of the carry returned by addListsHelper when adding lists representing 724 and 564?

easy

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Trace addition from least significant digit

   Adding 4 + 4 = 8, carry 0; next 2 + 6 = 8, carry 0; finally 7 + 5 = 12, carry 1.

2. Step 2: Propagate carry backward

   Carry 1 is returned from the most significant digit addition, indicating an overflow digit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   724 + 564 = 1288, carry 1 at MSB addition [OK]

Hint: Carry is from MSB addition overflow [OK]

Common Mistakes:

• Ignoring carry from most significant digit
• Off-by-one error in recursion base case
• Misaligning lists before addition

2. Consider the following code snippet implementing the two-pointer approach to find the intersection of two linked lists. Given the lists: listA: 1 -> 2 -> 3 -> 4 -> 5 listB: 9 -> 4 -> 5 where nodes with values 4 and 5 are shared (intersection starts at node with value 4). What is the value returned by the function?

easy

A. 3

B. 4

C. 5

D. No intersection

Solution

1. Step 1: Trace pointers through lists

   pA starts at 1, pB at 9. They advance until pA reaches 4, pB reaches 4 (intersection node). Since nodes are shared, pA is pB at node with value 4.

2. Step 2: Confirm return value

   The function returns the intersection node, which has value 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Intersection node value is 4 as expected [OK]

Hint: Pointers meet at shared node 4 [OK]

Common Mistakes:

• Returning node value instead of node reference
• Confusing next pointers
• Off-by-one in pointer switching

3. Consider the following Python code implementing the optimal merge K sorted lists approach using a min-heap. Given the input lists: [1->4->5], [1->3->4], [2->6], what is the value of current.next.val after the third iteration of the while loop?

easy

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Initialize heap with heads: 1,1,2

   Heap order: [1,1,2]

2. Step 2: Iterations of while loop

   1st pop: smallest=1 (from first list), push 4; 2nd pop: smallest=1 (from second list), push 3; 3rd pop: smallest=2 (from third list), push 6. After 3rd iteration, current.next.val = 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Third extracted node value is 2 [OK]

Hint: Track heap pops and pushed next nodes carefully [OK]

Common Mistakes:

• Off-by-one iteration counting
• Confusing which node is popped
• Forgetting to push next nodes

4. Identify the bug in the following code snippet intended to find the intersection node of two singly linked lists using the two-pointer approach:

medium

A. Line 6: Using '!=' instead of 'is not' to compare nodes

B. Line 8: Not checking if headA or headB is None before starting

C. Line 9: Incorrectly resetting pA and pB to headB and headA respectively

D. Line 10: Returning pA instead of pB

Solution

1. Step 1: Understand node comparison

   Nodes must be compared by reference, not by value. Using '!=' compares values, not references, causing incorrect intersection detection.

2. Step 2: Identify correct comparison operator

   'is not' compares object identity, ensuring correct detection of intersection node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using '!=' causes false positives or misses intersection [OK]

Hint: Use 'is' or 'is not' to compare nodes, not '==' or '!=' [OK]

Common Mistakes:

• Comparing node values instead of references
• Forgetting to handle empty lists
• Infinite loops due to pointer reset errors

5. Suppose the digits in the input linked lists are stored in forward order (most significant digit first). Which modification to the in-place iterative addition algorithm is necessary to correctly add the two numbers?

hard

A. Traverse both lists once, adding digits directly without reversing, handling carry forward.

B. Create new nodes for the sum since in-place modification is impossible with forward order.

C. Use recursion to add digits from head to tail, passing carry backward.

D. Reverse both input lists, apply the in-place addition, then reverse the result list back.

Solution

1. Step 1: Understand forward order challenge

   Digits stored most significant first require addition from tail to head to handle carry properly.

2. Step 2: Reverse input lists

   Reversing both lists converts them to reverse order, allowing reuse of the in-place addition algorithm.

3. Step 3: Reverse result list

   After addition, reverse the result to restore forward order.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Reversing lists enables correct carry handling in forward order [OK]

Hint: Reverse lists to reuse reverse-order addition logic [OK]

Common Mistakes:

• Trying to add forward order lists without reversing
• Assuming carry can be handled left-to-right easily
• Creating new lists unnecessarily