Remove N-th Node from the End of a Linked List | Java

Given the head of a singly linked list and an integer n, remove the n-th node from the end of the list and return the head of the resulting list.

Removing the N-th node from the end of a singly linked list is a classic interview/algorithm problem. It tests your understanding of pointers, edge-case handling (removing the head) and different trade-offs between time/space approaches.

Example 1

Input: head = [1,2,3,4,5], n = 2
  Output: [1,2,3,5]
  Explanation: The 2nd node from the end is 4, so remove it.

Example 2

Input: head = [1], n = 1
  Output: []
  Explanation: Removing the only node yields an empty list.

Example 3

Input: head = [1,2], n = 2
  Output: [2]
  Explanation: The 2nd from end is the head (1), so new head is 2.

Constraints (typical)

• Number of nodes: 1 <= length(head) <= 10^5 (can vary by platform)

• Node values: arbitrary (e.g., -1000 <= Node.val <= 1000)

• 1 <= n <= length(head)

Approaches to Solve the Problem

We'll solve this problem step by step, starting with the basic brute-force method, then making it faster with improvements and finally reaching the best one-pass solution.

Approach 1: Brute Force (Two-pass)

Idea:

• Traverse once to calculate the length L of the linked list.

• Compute the index to remove → L - n.

• Traverse again to that index and remove the node.

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

public class RemoveNthNode {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        int index = length - n;
        if (index == 0) return head.next;
        curr = head;
        for (int i = 1; i < index; i++) {
            curr = curr.next;
        }
        curr.next = curr.next.next;
        return head;
    }
}

Complexity:

• Time: O(L) (two passes)

• Space: O(1)

Approach 2: Using a Stack

• Traverse the list and push every node onto a stack.

• Pop n times - the popped node is the target.

• The node left on top of the stack (if any) is the one just before the target. Adjust its pointer to skip the target node.

• If the stack is empty after popping, it means we removed the head node.

• We'll also handle the edge case where n is greater than the list length.

import java.util.Stack;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class RemoveNthNodeStack {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = head;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }
        if (n > stack.size()) {
            return head; // invalid input : return original list
        }
        for (int i = 0; i < n; i++) {
            curr = stack.pop();
        }
        if (stack.isEmpty()) {
            return head.next;
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return head;
    }
}

Complexity:

• Time Complexity: O(L) -> traverse once + pop at most n times.

• Space Complexity: O(L) -> store all nodes in the stack.

Approach 3: Recursive

Instead of iterating with loops, we use recursion. The recursion naturally processes the list from end to start during backtracking. This makes it easy to count nodes from the end without explicitly knowing the list length.

Recursive DFS: Each recursive call goes deeper into the list until null.

Backtracking Phase: When recursion unwinds, we start counting nodes from the end (pos = dfs(next) + 1).

Delete at n-th Node: When the counter reaches n+1, we know the current node is just before the one we want to remove.

We update the link:

node.next = node.next.next;

Why Use a Dummy Node?

• If the head itself needs removal (n == length), recursion would fail without a dummy.

• The dummy node ensures we always have a reference before head, making deletion safe.

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

public class RemoveNthNodeRecursive {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        dfs(dummy, n);
        return dummy.next;
    }
    private int dfs(ListNode node, int n) {
        if (node == null) return 0;
        int pos = dfs(node.next, n) + 1;
        if (pos == n + 1) {
            node.next = node.next.next;
        }
        return pos;
    }
}

Complexity Analysis

• Time Complexity: O(L), where L = length of the list (each node visited once).

• Space Complexity: O(L) due to recursion stack (not as memory efficient as iterative approaches).

Approach 4: Two-Pointer (Optimal One-Pass)

We want to remove the n-th node from the end of a linked list. Instead of counting length first, we use two pointers (fast and slow):

Dummy Node

• Create a dummy node before the head.
• This makes edge cases (like removing the head) simpler.

Move fast n+1 steps ahead

• Keep slow at dummy.
• Now the gap between fast and slow is n+1.

Move both pointers together

• Until fast reaches the end (null).
• At this point, slow will be at the node just before the target node.

Delete the node

• By skipping it: slow.next = slow.next.next;

Why n+1 Steps?

We want slow to stop at the node before the one we're deleting. So the gap must be n+1 steps (not just n).

Edge Cases

• List is empty : return null.

• n equals list length : remove the head.

• n is larger than list length : either return original list or throw exception (depends on requirement).

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

public class RemoveNthNodeTwoPointer {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        for (int i = 0; i <= n; i++) {
            if (fast == null) {
                return head;
            }
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

Complexity Analysis

• Time Complexity: O(L), where L = length of list (single pass).

• Space Complexity: O(1), since we only use two pointers.

Complexity Comparison Table