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 target from the end, then remove the target node by skipping it.

Execution Sample

DSA C++

ListNode* removeNthFromEnd(ListNode* head, int n) {
  ListNode dummy(0);
  dummy.next = head;
  ListNode* first = &dummy;
  ListNode* second = &dummy;
  for (int i = 0; i <= n; ++i) first = first->next;
  while (first != nullptr) {
    first = first->next; second = second->next;
  }
  second->next = second->next->next;
  return dummy.next;
}

This code removes the nth node from the end of a singly linked list using two pointers.

Execution Table

Step	Operation	First Pointer Position	Second Pointer Position	List Nodes	Pointer Changes	Visual State
1	Create dummy node pointing to head	dummy	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	dummy.next = head	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
2	Initialize first and second at dummy	dummy	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first = dummy, second = dummy	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
3	Move first pointer 1 step (i=0)	1	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first = first->next	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
4	Move first pointer 2 steps (i=1)	2	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first = first->next	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
5	Move first pointer 3 steps (i=2)	3	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first = first->next	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
6	Move first pointer 4 steps (i=3)	4	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first = first->next	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
7	Move first pointer 5 steps (i=4)	5	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first = first->next	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
8	Move first pointer 6 steps (i=5)	null	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first = first->next	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
9	First is null, start moving both pointers	null	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	No move, first is null	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
10	Since first is null, stop moving pointers	null	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	Stop loop	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
11	Remove node after second (which is head)	null	dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	second->next = second->next->next	dummy(0) -> 2 -> 3 -> 4 -> 5 -> null
12	Return dummy.next as new head	null	dummy	2 -> 3 -> 4 -> 5 -> null	Return dummy.next	2 -> 3 -> 4 -> 5 -> null

💡 first pointer reached null, second pointer is before target node, removal done

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 11	Final
first	dummy	1	2	3	4	5	null	null	null
second	dummy	dummy	dummy	dummy	dummy	dummy	dummy	dummy	dummy
list	1 -> 2 -> 3 -> 4 -> 5 -> null	same	same	same	same	same	same	2 -> 3 -> 4 -> 5 -> null	2 -> 3 -> 4 -> 5 -> null

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, as shown in steps 1 and 11.

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

Moving first pointer n+1 steps ahead ensures the second pointer stops exactly before the node to remove. This is clear in steps 3 to 8 where first moves ahead, and in step 11 where second->next is removed.

What happens if the list has only one node and n=1?

The dummy node points to the single node. After moving pointers, second points to dummy, and removing second->next removes the only node, resulting in an empty list. This is handled by the dummy node and pointer logic.

Visual Quiz - 3 Questions

Look at the execution table, what is the position of the first pointer after step 5?

A Node with value 3

B Node with value 2

C Node with value 4

D dummy node

💡 Hint

Check the 'First Pointer Position' column at step 5 in the execution table.

At which step does the second pointer move from dummy to the next node?

A Step 9

B It never moves from dummy

C Step 10

D Step 11

💡 Hint

Look at the 'Second Pointer Position' column in the execution table; it stays at dummy until removal.

If n was 2 instead of 1, how would the pointer positions change after moving first pointer n+1 steps?

A First pointer would be at node with value 5

B First pointer would be at node with value 3

C First pointer would be at node with value 4

D First pointer would be null

💡 Hint

Moving first pointer n+1 steps means 3 steps for n=2; check steps 3-8 for n=1 and adjust accordingly.

Concept Snapshot

Remove Nth Node from End of List:
- Use dummy node before head to simplify edge cases.
- Set two pointers at dummy.
- Move first pointer n+1 steps ahead.
- Move both pointers until first reaches end.
- Second pointer points before target node.
- Remove target by second->next = second->next->next.
- Return dummy.next as new head.

Full Transcript

This concept shows how to remove the nth node from the end of a singly linked list using two pointers. We start by creating a dummy node pointing to the head to handle edge cases like removing the head itself. Two pointers, first and second, start at the dummy. We move the first pointer n+1 steps ahead so that when the first pointer reaches the end, the second pointer is right before the node to remove. Then, we remove the target node by changing second->next to skip it. Finally, we return dummy.next as the new head of the list. The execution table traces each pointer move and the list state, showing how the pointers move and how the list changes after removal. Key moments clarify why the dummy node is needed and why the first pointer moves n+1 steps. The visual quiz tests understanding of pointer positions and the effect of changing n.

Practice

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

easy

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

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

C. Reverse the linked list

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

Solution

1. Step 1: Understand the problem statement

   The problem asks to remove the node that is Nth from the end of the linked list, not from the start or to reverse or add nodes.

2. Step 2: Clarify the operation on the list

   Removing the Nth node from the end means counting nodes from the tail backwards and deleting that node.

3. Final Answer:

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

4. Quick Check:

   Remove Nth from end = Remove Nth from end [OK]

Hint: Focus on counting nodes from the list's end, not start [OK]

Common Mistakes:

• Confusing Nth from end with Nth from start
• Thinking the problem asks to reverse the list
• Trying to add nodes instead of removing

2. Which of the following C++ function signatures correctly represents a function to remove the Nth node from the end of a singly linked list?

easy

A. ListNode* removeNthFromEnd(ListNode* head, int n);

B. void removeNthFromEnd(int n, ListNode* head);

C. ListNode removeNthFromEnd(ListNode head, int n);

D. ListNode* removeNthFromEnd(int n);

Solution

1. Step 1: Check parameter order and types

   The function should take the head pointer of the list and the integer n as parameters, with head first and n second.

2. Step 2: Check return type

   Since the head might change (if first node is removed), the function returns a pointer to the new head.

3. Final Answer:

   ListNode* removeNthFromEnd(ListNode* head, int n); -> Option A

4. Quick Check:

   Correct signature = ListNode* removeNthFromEnd(ListNode* head, int n); [OK]

Hint: Function returns new head pointer and takes head, n as parameters [OK]

Common Mistakes:

• Wrong parameter order
• Returning ListNode instead of pointer
• Missing head parameter

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 -> 3 -> 5 -> null

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

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

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

Solution

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

   Counting from the end: 5 (1st), 4 (2nd). So node with value 4 is to be removed.

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

   Node 3's next pointer now points to node 5, skipping node 4.

3. Final Answer:

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

4. Quick Check:

   Remove 2nd from end = Remove node 4 [OK]

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

Common Mistakes:

• Removing wrong node counting from start
• Not updating links correctly
• Confusing 2nd from end with 2nd from start

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

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

medium

A. Uses wrong loop condition in for loop

B. Does not handle case when n equals list length (removing head)

C. Returns wrong pointer type

D. Does not move slow pointer at all

Solution

1. Step 1: Analyze fast pointer movement

   Fast pointer moves n steps ahead. If n equals list length, fast becomes nullptr.

2. Step 2: Check while loop condition

   While loop uses fast->next, but if fast is nullptr, accessing fast->next causes error. Also, removing head node is not handled.

3. Final Answer:

   Does not handle case when n equals list length (removing head) -> Option B

4. Quick Check:

   Edge case for head removal missing [OK]

Hint: Check edge cases when fast pointer reaches null early [OK]

Common Mistakes:

• Ignoring removal of head node
• Accessing fast->next without null check
• Not updating head pointer when needed

5. You want to remove the 3rd node from the end of a linked list with nodes: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null. Which of the following steps correctly describes the process using two pointers?

hard

A. Move slow pointer 3 steps ahead, then move fast pointer until slow reaches end, then remove fast's next node.

B. Move fast pointer 3 steps ahead, then move slow pointer 3 steps ahead, then remove head node.

C. Move fast pointer 3 steps ahead, then move both pointers until fast reaches end, then remove slow's next node.

D. Move both pointers together from start without offset, then remove the node at position 3.

Solution

1. Step 1: Initialize two pointers at head

   Start both fast and slow pointers at the head of the list.

2. Step 2: Move fast pointer n steps ahead

   Move fast pointer 3 steps ahead to create a gap of 3 nodes between fast and slow.

3. Step 3: Move both pointers until fast reaches end

   Move fast and slow pointers one step at a time until fast reaches the last node.

4. Step 4: Remove the node after slow pointer

   Slow pointer now points to node before the target; remove slow->next node.

5. Final Answer:

   Move fast pointer 3 steps ahead, then move both pointers until fast reaches end, then remove slow's next node. -> Option C

6. Quick Check:

   Two-pointer gap method = Move fast pointer 3 steps ahead, then move both pointers until fast reaches end, then remove slow's next node. [OK]

Hint: Use two pointers with gap n to find node before target [OK]

Common Mistakes:

• Moving slow pointer first instead of fast
• Removing wrong node after pointers move
• Not creating correct gap between pointers