Remove Nth Node from End of List in DSA Python - Execution Trace

Concept Flow - Remove Nth Node from End of List

Create dummy node pointing to head

↓

Set two pointers: first and second at dummy

↓

Move first pointer n+1 steps ahead

↓

Move first and second pointers together until first reaches end

↓

Second pointer now before target node

↓

Remove target node by changing second.next

↓

Return dummy.next as new head

We use two pointers spaced n+1 apart to find the node before the target, then remove the target node.

Execution Sample

DSA Python

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    first = dummy
    second = dummy
    for _ in range(n+1):
        first = first.next
    while first:
        first = first.next
        second = second.next
    second.next = second.next.next
    return dummy.next

Removes the nth node from the end of a singly linked list using two pointers.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create dummy node pointing to head	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	dummy -> 0, dummy.next -> 1	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
2	Set first and second pointers at dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first = dummy(0), second = dummy(0)	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
3	Move first pointer n+1=3 steps ahead	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first moves: 0->1, 1->2, 2->3	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
4	Move first and second pointers together until first reaches end	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first: 3->4, 4->5, 5->null; second: 0->1, 1->2, 2->3	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
5	Second pointer now before target node (3)	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	second at node 3	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
6	Remove target node by changing second.next	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	second.next changes from 4 to 5 (skips 4)	dummy(0) -> 1 -> 2 -> 3 -> 5 -> null
7	Return dummy.next as new head	1 -> 2 -> 3 -> 5 -> null	head updated to node 1	1 -> 2 -> 3 -> 5 -> null

💡 first pointer reached end (null), loop ends, target node removed

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	Final
dummy	node(0) -> 1	node(0) -> 1	node(0) -> 1	node(0) -> 1	node(0) -> 1
first	node(0)	node(3)	null	null	null
second	node(0)	node(0)	node(3)	node(3)	node(3)
head	node(1)	node(1)	node(1)	node(1)	node(1)
List Length	6	6	6	5	5

Key Moments - 3 Insights

Why do we create a dummy node before the head?

The dummy node helps handle cases where the head itself is removed. It simplifies pointer changes by always having a node before the target. See Step 1 and Step 7 in execution_table.

Why move the first pointer n+1 steps ahead, not just n?

Moving first pointer n+1 steps ahead keeps the gap so that when first reaches the end, second is just before the node to remove. This is shown in Step 3 and Step 4.

What happens if n equals the length of the list?

Then the node to remove is the head. The dummy node allows second pointer to be before head, so removal works the same. This is why dummy is important (Step 1 and Step 7).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, where is the first pointer after moving n+1 steps?

A At node 2

B At node 3

C At node 4

D At dummy node

💡 Hint

Check the 'Pointer Changes' column in Step 3 of execution_table.

At which step does the second pointer move to the node before the target node?

A Step 5

B Step 4

C Step 2

D Step 6

💡 Hint

Look for when 'second at node 3' appears in execution_table.

If we remove the 1st node from the end (n=1), how would Step 6's pointer change differ?

A first pointer would not move

B second.next would skip the head node

C second.next would skip the last node

D dummy node would be removed

💡 Hint

Think about which node is removed when n=1 and check Step 6 pointer change.

Concept Snapshot

Remove Nth Node from End of List:
- Use dummy node before head
- Set two pointers at dummy
- Move first pointer n+1 steps ahead
- Move both pointers until first reaches end
- second.next skips target node
- Return dummy.next as new head

Full Transcript

This concept removes the nth node from the end of a singly linked list. We start by creating a dummy node pointing to the head to handle edge cases. Two pointers, first and second, start at the dummy. We move the first pointer n+1 steps ahead to maintain a gap. Then we move both pointers forward until the first reaches the end. At this point, the second pointer is just before the node to remove. We remove the target node by changing second.next to skip it. Finally, we return dummy.next as the new head of the list. This method works even if the head node is removed.