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 before target node

↓

Change second.next to skip target node

↓

Return dummy.next as new head

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

Execution Sample

DSA C#

ListNode dummy = new ListNode(0, head);
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;

This code removes the nth node from the end by using two pointers to find it.

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=head(0), first=dummy, second=dummy	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
2	Move first pointer n+1=3 steps ahead	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first moves: dummy(0) -> 1 -> 2	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
3	Move first and second until first reaches end	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first: 2->3->4->5->null, second: 0->1->2	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
4	Second pointer before target node (node 3)	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	second at node 2, target node is second.next (3)	dummy(0) -> 1 -> 2 -> [3] -> 4 -> 5 -> null
5	Remove target node by skipping it	0 -> 1 -> 2 -> 4 -> 5 -> null	second.next changed from 3 to 4	dummy(0) -> 1 -> 2 -> 4 -> 5 -> null
6	Return dummy.next as new head	1 -> 2 -> 4 -> 5 -> null	head updated to node 1	1 -> 2 -> 4 -> 5 -> null
7	End	1 -> 2 -> 4 -> 5 -> null	No pointer changes	1 -> 2 -> 4 -> 5 -> null

💡 first pointer reached null, second pointer is before node to remove

Variable Tracker

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

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, as shown in step 1 and step 6 of the execution_table.

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

Moving first pointer n+1 steps ahead ensures the second pointer stops just before the node to remove, as seen in step 2 and step 4.

How do we know which node to remove?

When first pointer reaches the end (null), second pointer is just before the target node, so second.next is removed (step 4 and 5).

Visual Quiz - 3 Questions

Look at the execution_table at step 2, where is the first pointer located?

A At dummy node

B At node 2

C At node 3

D At null

💡 Hint

Check the 'Pointer Changes' column in step 2 of execution_table.

At which step does the list visually change by removing a node?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Visual State' column to see when node 3 disappears.

If n was 1 instead of 2, how would the first pointer move in step 2?

A It would move 2 steps ahead

B It would move 3 steps ahead

C It would move 1 step ahead

D It would not move

💡 Hint

Recall first pointer moves n+1 steps ahead; n=1 means 2 steps.

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 is before target node
- Skip target node by changing second.next
- Return dummy.next as new head

Full Transcript

To remove the nth node from the end of a linked list, we first create a dummy node pointing to the head. We set two pointers, first and second, at the dummy. We move the first pointer n+1 steps ahead so that when it reaches the end, the second pointer is just before the node to remove. Then, we move both pointers forward together until the first pointer reaches the end of the list. At this point, the second pointer's next node is the target node to remove. We skip this node by changing second.next to second.next.next. Finally, we return dummy.next as the new head of the list. This method handles edge cases like removing the head node smoothly.

Practice

1. What does the problem Remove Nth Node from End of List ask you to do?

easy

A. Delete the node that is the nth from the end in a linked list

B. Add a new node at the nth position from the start

C. Reverse the linked list

D. Find the value of the nth node from the start

Solution

1. Step 1: Understand the problem statement

   The problem asks to remove the node that is nth from the end of a singly linked list.

2. Step 2: Clarify what removal means

   Removal means unlinking that node so the list skips it, keeping the rest intact.

3. Final Answer:

   Delete the node that is the nth from the end in a linked list -> Option A

4. Quick Check:

   Remove nth from end = Delete nth from end [OK]

Hint: Focus on 'remove nth from end' means delete that node [OK]

Common Mistakes:

• Confusing nth from end with nth from start
• Thinking it means reversing the list
• Trying to find value instead of removing node

2. Which of the following C# code snippets correctly declares a singly linked list node class for this problem?

easy

A. public class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }

B. class Node { int val; Node next; Node(int x) { val = x; next = null; } }

C. public struct ListNode { public int val; public ListNode next; }

D. public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } }

Solution

1. Step 1: Check for public access modifiers

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } uses public class and public members, which is correct for external access.

2. Step 2: Verify constructor and member initialization

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } correctly initializes val and next in constructor; others miss public or use struct incorrectly.

3. Final Answer:

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } -> Option D

4. Quick Check:

   Proper class with public members = public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } [OK]

Hint: Use public class and public members for linked list nodes [OK]

Common Mistakes:

• Missing public keyword causing access errors
• Using struct instead of class for linked list node
• Not initializing next to null in constructor

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

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

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

D. 2 -> 3 -> 4 -> 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

   Link node 3's next to node 5, skipping node 4. Result: 1->2->3->5->null.

3. Final Answer:

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

4. Quick Check:

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

Hint: Count from end to find node, then skip it [OK]

Common Mistakes:

• Removing the wrong node counting from start
• Removing node with value 3 instead of 4
• Not updating links correctly causing broken list

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

public 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 != null) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return head;
}

medium

A. Does not handle case when fast becomes null after initial loop

B. Uses slow pointer incorrectly by moving it too early

C. Returns slow instead of head

D. Does not update fast pointer inside the loop

Solution

1. Step 1: Analyze fast pointer movement

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

2. Step 2: Check for null fast before accessing fast.next

   Code does not check if fast is null before while loop, causing NullReferenceException.

3. Final Answer:

   Does not handle case when fast becomes null after initial loop -> Option A

4. Quick Check:

   Null fast after n steps = bug [OK]

Hint: Check if fast is null after initial n steps [OK]

Common Mistakes:

• Ignoring null check for fast pointer
• Moving slow pointer before fast is properly positioned
• Returning wrong node as new head

5. You want to remove the 1st node from the end of a linked list with only one node: 10 -> null. What should the resulting list be?

hard

A. 10 -> null

B. null (empty list)

C. Error because list is too short

D. 10 -> 10 -> null

Solution

1. Step 1: Understand removing 1st node from end in single-node list

   Removing last node means list becomes empty.

2. Step 2: Resulting list after removal

   Since only node is removed, list is now null (empty).

3. Final Answer:

   null (empty list) -> Option B

4. Quick Check:

   Remove only node = empty list [OK]

Hint: Removing last node in single-node list empties it [OK]

Common Mistakes:

• Returning original list instead of empty
• Expecting error instead of empty list
• Trying to access next node which does not exist