Remove Nth Node from End of List in DSA C#

Mental Model

To remove the nth node from the end, we find the node just before it by moving two pointers with a gap of n nodes.

Analogy: Imagine two friends walking on a path where one starts n steps ahead. When the front friend reaches the end, the other is right before the target to remove.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑         ↑
        slow      fast

Dry Run Walkthrough

Input: list: 1->2->3->4->5, remove 2nd node from end

Goal: Remove the 2nd node from the end, which is node with value 4

Step 1: Move fast pointer n=2 steps ahead

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
          slow ↑         fast ↑

Why: To create a gap of n nodes between slow and fast pointers

Step 2: Move both slow and fast pointers one step until fast reaches end

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
               slow ↑           fast ↑

Why: To position slow pointer just before the node to remove

Step 3: Move both pointers one more step

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                    slow ↑             fast ↑

Why: Continue moving to reach the node before target

Step 4: Fast pointer reached end; slow is before node 4 to remove

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                    slow ↑                   fast null

Why: Slow is at node 3, just before node 4 to remove

Step 5: Remove node after slow by linking slow.next to slow.next.next

head -> 1 -> 2 -> 3 -> 5 -> null

Why: Node 4 is removed by skipping it in the list

Result:

head -> 1 -> 2 -> 3 -> 5 -> null

Annotated Code

DSA C#

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head); // dummy node before head
        ListNode slow = dummy;
        ListNode fast = dummy;

        // Move fast pointer n steps ahead
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // Move both pointers until fast reaches the end
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // Remove nth node from end
        slow.next = slow.next.next;

        return dummy.next;
    }

    public static void PrintList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            Console.Write(curr.val);
            if (curr.next != null) Console.Write(" -> ");
            curr = curr.next;
        }
        Console.WriteLine(" -> null");
    }

    public static void Main() {
        // Create list 1->2->3->4->5
        ListNode head = new ListNode(1,
            new ListNode(2,
                new ListNode(3,
                    new ListNode(4,
                        new ListNode(5)))));

        Solution sol = new Solution();
        int n = 2;
        ListNode result = sol.RemoveNthFromEnd(head, n);
        PrintList(result);
    }
}

ListNode dummy = new ListNode(0, head); // dummy node before head

Create dummy node to handle edge cases like removing head

for (int i = 0; i < n; i++) { fast = fast.next; }

Advance fast pointer n steps ahead to create gap

while (fast.next != null) { slow = slow.next; fast = fast.next; }

Move both pointers until fast reaches last node

slow.next = slow.next.next;

Remove nth node by skipping it in the list

Output

1 -> 2 -> 3 -> 5 -> null

Complexity Analysis

Time: O(n) because we traverse the list once with two pointers

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Compared to counting length first then removing, this uses one pass instead of two, making it more efficient

Edge Cases

Removing the head node (n equals list length)

Dummy node allows removal without special case; head is updated correctly

DSA C#

ListNode dummy = new ListNode(0, head); // dummy node before head

List with only one node and n=1

Returns null as list becomes empty after removal

DSA C#

slow.next = slow.next.next;

n is 1 (remove last node)

Slow pointer stops at second last node and removes last node correctly

DSA C#

while (fast.next != null) { slow = slow.next; fast = fast.next; }

When to Use This Pattern

When asked to remove the nth node from the end in a single pass, use two pointers with a gap of n to find the target efficiently.

Common Mistakes

Mistake: Not using a dummy node and failing when removing the head node
Fix: Add a dummy node before head to simplify removal logic

Mistake: Moving fast pointer n+1 steps instead of n, causing null reference
Fix: Move fast pointer exactly n steps ahead before moving both pointers

Summary

Removes the nth node from the end of a singly linked list in one pass.

Use when you need efficient single-pass removal without counting list length first.

Use two pointers spaced n apart to find the node before the target for removal.

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