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.

Practice

1. What does the problem "Remove Nth Node from End of List" ask you to do with a linked list?

easy

A. Remove the node that is Nth from the end of the list

B. Remove the node that is Nth from the start of the list

C. Add a new node at the Nth position from the end

D. Reverse the linked list up to the Nth node from the end

Solution

1. Step 1: Understand the problem statement

   The problem requires removing the node that is exactly N positions from the end of the linked list.

2. Step 2: Clarify the difference from other options

   Options A, C, and D describe different operations: removing from start, adding nodes, or reversing, which are not asked here.

3. Final Answer:

   Remove the node that is Nth from the end of the list -> Option A

4. Quick Check:

   Remove Nth from end = Remove the node that is Nth from the end of the list [OK]

Hint: Focus on 'Nth from end' means counting backward [OK]

Common Mistakes:

• Confusing Nth from start with Nth from end
• Thinking the problem asks to add nodes
• Assuming the list needs reversing

2. Which of the following is the correct way to declare a pointer to the head of a singly linked list in C?

easy

A. struct Node head*;

B. Node head*;

C. struct Node* head;

D. Node* head;

Solution

1. Step 1: Recall C struct pointer syntax

   In C, to declare a pointer to a struct Node, use 'struct Node* head;'.

2. Step 2: Identify incorrect syntax

   Options A, B, and D misuse the order or omit 'struct' keyword which is required unless typedef is used.

3. Final Answer:

   struct Node* head; -> Option C

4. Quick Check:

   Pointer to struct Node = struct Node* head; [OK]

Hint: Remember 'struct' keyword before struct name in C [OK]

Common Mistakes:

• Omitting 'struct' keyword in declaration
• Placing '*' incorrectly after variable name
• Using typedef name without defining it

3. What will be the output linked list after removing the 2nd node from the end in the list: 1 -> 2 -> 3 -> 4 -> 5 -> null?

medium

A. 1 -> 2 -> 4 -> 5 -> null

B. 2 -> 3 -> 4 -> 5 -> null

C. 1 -> 3 -> 4 -> 5 -> null

D. 1 -> 2 -> 3 -> 5 -> null

Solution

1. Step 1: Identify the 2nd node from the end

   The list is 1->2->3->4->5. Counting from end: 5 (1st), 4 (2nd). So node with value 4 is to be removed.

2. Step 2: Remove node with value 4 and link previous to next

   After removal, the list becomes 1->2->3->5->null.

3. Final Answer:

   1 -> 2 -> 3 -> 5 -> null -> Option D

4. Quick Check:

   Remove 2nd from end (4) = 1->2->3->5->null [OK]

Hint: Count nodes from end to find which to remove [OK]

Common Mistakes:

• Removing the wrong node counting from start
• Skipping the link update after removal
• Confusing 2nd from end with 2nd from start

4. Given the following code snippet to remove the Nth node from end, what is the error?

struct Node* removeNthFromEnd(struct Node* head, int n) {
    struct Node* fast = head;
    struct Node* slow = head;
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
    while (fast->next != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return head;
}

medium

A. The slow pointer is moved too many times causing segmentation fault

B. The loop does not check if fast becomes NULL before accessing fast->next

C. The function does not handle the case when n is zero

D. The function returns the wrong pointer instead of head

Solution

1. Step 1: Analyze the for loop moving fast pointer

   The loop moves fast pointer n times without checking if fast is NULL, which can cause a crash if n is larger than list length.

2. Step 2: Check while loop condition and pointer usage

   The while loop uses fast->next without null check before the loop, which is unsafe if fast is NULL.

3. Final Answer:

   The loop does not check if fast becomes NULL before accessing fast->next -> Option B

4. Quick Check:

   Missing NULL check on fast pointer causes error [OK]

Hint: Always check pointers for NULL before dereferencing [OK]

Common Mistakes:

• Not checking if fast is NULL before fast->next
• Assuming list length is always >= n
• Ignoring edge case when removing head node

5. You have a linked list: 10 -> 20 -> 30 -> 40 -> 50 -> null. You want to remove the 5th node from the end. What will be the resulting list?

hard

A. 20 -> 30 -> 40 -> 50 -> null

B. 10 -> 20 -> 30 -> 40 -> null

C. 10 -> 20 -> 30 -> 40 -> 50 -> null (no change)

D. 30 -> 40 -> 50 -> null

Solution

1. Step 1: Identify the 5th node from the end

   The list length is 5, so the 5th node from the end is the first node with value 10.

2. Step 2: Remove the head node and update head pointer

   Removing the first node results in the list: 20 -> 30 -> 40 -> 50 -> null.

3. Final Answer:

   20 -> 30 -> 40 -> 50 -> null -> Option A

4. Quick Check:

   Remove 5th from end (head) = list without first node [OK]

Hint: Removing N equals list length means remove head [OK]

Common Mistakes:

• Not updating head pointer when removing first node
• Confusing Nth from end with Nth from start
• Assuming no change if N equals list length