Remove Nth Node from End of List in DSA C - 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 points to node before target

↓

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 one to remove, then adjust pointers to remove it.

Execution Sample

DSA C

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode dummy = {0, head};
    struct ListNode *first = &dummy, *second = &dummy;
    for (int i = 0; i <= n; i++) first = first->next;
    while (first != NULL) {
        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	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL	dummy points to head (1), first = dummy, second = dummy	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
2	Move first pointer n+1=3 steps ahead	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL	first moves: dummy->1->2->3	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL (first at 3, second at dummy)
3	Move first and second pointers until first reaches NULL	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL	first: 3->4->5->NULL, second: dummy->1->2	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL (first at NULL, second at 2)
4	Remove node after second (node 3)	dummy(0) -> 1 -> 2 -> 4 -> 5 -> NULL	second->next changed from 3 to 4	dummy(0) -> 1 -> 2 -> 4 -> 5 -> NULL
5	Return dummy.next as new head	1 -> 2 -> 4 -> 5 -> NULL	head updated to dummy.next (1)	1 -> 2 -> 4 -> 5 -> NULL
6	Exit	List updated with nth node from end removed	No pointer changes	1 -> 2 -> 4 -> 5 -> NULL

💡 first pointer reached NULL, removal done, list updated

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
first	dummy(0)	3	NULL	NULL	NULL
second	dummy(0)	dummy(0)	2	2	2
dummy.next (head)	1	1	1	1	1
List Size	5	5	5	4	4

Key Moments - 3 Insights

Why do we move the first pointer n+1 steps ahead instead of n?

Moving first pointer n+1 steps ahead ensures second pointer stops at the node before the target node, allowing easy removal by changing second->next (see execution_table step 2 and 3).

What happens if the node to remove is the head node?

Using a dummy node before head handles this case smoothly. The second pointer will point to dummy, and removal adjusts dummy->next, effectively changing the head (see execution_table step 4 and 5).

Why do we return dummy.next instead of head?

Because the head might be removed, dummy.next always points to the updated list start, ensuring correct return (see execution_table step 5).

Visual Quiz - 3 Questions

Look at the execution_table, what node is the first pointer at after moving n+1 steps in step 2?

A Node with value 2

B Node with value 3

C Node with value 4

D NULL

💡 Hint

Check execution_table row for step 2 under Pointer Changes and Visual State

At which step does the second pointer point to the node before the one to remove?

A Step 3

B Step 4

C Step 1

D Step 5

💡 Hint

Look at execution_table rows for step 3 and 4, see where second pointer is

If n was 1 (remove last node), how would the pointer movement change in step 2?

A first pointer moves 1 step ahead

B first pointer moves 3 steps ahead

C first pointer moves 2 steps ahead

D first pointer does not move

💡 Hint

Recall first pointer moves n+1 steps ahead, see step 2 for n=2 example

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 points before target node
- Remove target by second->next = second->next->next
- Return dummy.next as new head

Full Transcript

This concept removes the nth node from the end of a singly linked list by using two pointers. First, a dummy node is created before the head to handle edge cases. Two pointers, first and second, start at the dummy. The first pointer moves n+1 steps ahead. Then both pointers move together until the first pointer reaches the end. At this point, the second pointer is just before the node to remove. The node is removed by changing second's next pointer to skip the target node. Finally, dummy.next is returned as the new head of the list. This method handles cases where the head node is removed and ensures safe pointer manipulation.