Remove Nth Node from End of List in DSA Java

Mental Model

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

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 friend to be removed.

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 4th node (2nd from end) so list becomes 1 -> 2 -> 3 -> 5

Step 1: Move fast pointer 2 steps ahead

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

Why: Create a gap of n=2 between fast and slow 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: Keep gap so slow points to node before target

Step 3: Move both pointers one more step

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

Why: Slow now points to node before the node to remove (4)

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

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

Why: Skip the 4th node to remove it

Result:

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

Annotated Code

DSA Java

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

public class Solution {
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0); // dummy node before head
        dummy.next = 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 the nth node from end
        slow.next = slow.next.next;

        return dummy.next;
    }

    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        // Create list 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        int n = 2;
        ListNode result = removeNthFromEnd(head, n);
        printList(result);
    }
}

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

Create dummy node to handle edge cases like removing head

ListNode slow = dummy; ListNode fast = dummy;

Initialize both pointers at dummy to maintain gap

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 from end by skipping it

Output

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

Complexity Analysis

Time: O(n) because we traverse the list twice at most (once to move fast pointer, once to move both pointers)

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

vs Alternative: Compared to counting length first and then removing node, this uses two pointers to do it in one pass, improving efficiency

Edge Cases

Removing the head node (n equals list length)

Dummy node allows removal without special case code

DSA Java

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

List with only one node and n=1

Returns null as list becomes empty

DSA Java

slow.next = slow.next.next;

n is 1 (remove last node)

Slow pointer stops at second last node and removes last node

DSA Java

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 of a linked list, use the two-pointer technique with a fixed gap to find the target node in one pass.

Common Mistakes

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

Mistake: Moving fast pointer n+1 steps instead of n, causing null pointer errors
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 to delete a node counting from the end without knowing the list length.

Keep two pointers with a gap of n so when the front pointer reaches the end, the other is just before the target.

Practice

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

easy

A. Reverse the entire linked list

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

C. Find the value of the Nth node from the start

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

Solution

1. Step 1: Understand the problem statement

   The problem requires removing the node that is Nth from the end of the linked list, not from the start.

2. Step 2: Clarify the operation on the list

   We do not add or reverse nodes; we specifically remove one node counting from the end.

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 'Nth from end' means counting backwards [OK]

Common Mistakes:

• Confusing Nth from end with Nth from start
• Thinking the problem asks to add or reverse nodes
• Ignoring the direction of counting nodes

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

easy

A. public ListNode removeNthFromEnd(ListNode head, int n)

B. public void removeNthFromEnd(int n, ListNode head)

C. public ListNode removeNode(ListNode head, int index)

D. public ListNode deleteNthNode(ListNode node, int n)

Solution

1. Step 1: Check method parameters and return type

   The method should take the head of the list and an integer n, and return the new head after removal.

2. Step 2: Match signature with problem requirements

   public ListNode removeNthFromEnd(ListNode head, int n) matches the expected signature: it takes (ListNode head, int n) and returns ListNode.

3. Final Answer:

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

4. Quick Check:

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

Hint: Method must return updated head and accept head, n as parameters [OK]

Common Mistakes:

• Wrong parameter order
• Void return type instead of ListNode
• Using incorrect parameter types

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. 1 -> 2 -> 3 -> 5 -> null

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

D. 2 -> 3 -> 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 with value 4 and link previous node to next

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

3. Final Answer:

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

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
• Off-by-one errors in counting
• Not updating links correctly after removal

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

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

medium

A. The for loop should run from i = 0 to i < n, not i <= n

B. The slow pointer should start at null, not head

C. The method should return slow, not head

D. The while loop condition should be fast.next != null

Solution

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

   The loop runs i from 0 to n inclusive (i <= n), moving fast n+1 steps, which is one step too many and causes NullPointerException.

2. Step 2: Correct the loop to run i < n to move fast exactly n steps ahead

   This ensures fast is n nodes ahead of slow, allowing correct removal of the target node.

3. Final Answer:

   The for loop should run from i = 0 to i < n, not i <= n -> Option A

4. Quick Check:

   Loop count off by one = The for loop should run from i = 0 to i < n, not i <= n [OK]

Hint: Check loop bounds carefully for pointer steps [OK]

Common Mistakes:

• Using i <= n instead of i < n in loop
• Starting slow pointer incorrectly
• Returning wrong node after removal

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 after removal?

hard

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

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

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

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

Solution

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

   Since the list has 5 nodes, the 5th from the end is the first node with value 10.

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

   Removing node 10 means the new head is node 20, so list becomes 20 -> 30 -> 40 -> 50 -> null.

3. Final Answer:

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

4. Quick Check:

   Remove first node = 20 -> 30 -> 40 -> 50 -> null [OK]

Hint: If N equals list length, remove head node [OK]

Common Mistakes:

• Not updating head when first node is removed
• Removing wrong node counting from end
• Confusing list length with N