Topics › Linked List › Medium Problems of LL

Remove Nth node from the back of the LL

Medium TUF ID 2849 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given the head of a singly linked list and an integer n. Remove the n-th node counted from the end (n = 1 is the tail, n = len is the head) and return the head of the resulting list. The follow-up asks for a single pass over the list.

Constraints: 1 ≤ len ≤ 3 × 10^4, 1 ≤ n ≤ len, values fit in a 32-bit signed integer. The Java solutions additionally leave the list unchanged when n is out of range, so they never throw.

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

Example 1

head = 1 -> 2 -> 3 -> 4 -> 5, n = 2
answer = 1 -> 2 -> 3 -> 5        // the 2nd from the end is 4

Example 2

head = 1 -> 2 -> 3 -> 4 -> 5, n = 5
answer = 2 -> 3 -> 4 -> 5        // the 5th from the end is the head

Example 3

head = 1, n = 1
answer = (empty)                 // removing the only node leaves nothing

Approach 1: Brute force, count then delete

Intuition. The n-th node from the back is the node at 0-based index len - n from the front. We cannot know len without a pass over the list, so count first, then walk to the node before index len - n and unlink its successor. Deleting the head is special because it has no predecessor: in that case the answer is simply head.next.

Algorithm.

1. Count the nodes to get len.
2. If n is out of range, return head unchanged.
3. If n == len, return head.next.
4. Walk len - n - 1 steps from head to reach the predecessor of the target.
5. Set predecessor.next = predecessor.next.next and return head.

static ListNode bruteForce(ListNode head, int n) {
    int len = 0;
    for (ListNode t = head; t != null; t = t.next) len++;
    if (n <= 0 || n > len) return head;          // nothing sensible to remove
    if (n == len) return head.next;              // the target is the head itself
    ListNode t = head;
    for (int i = 0; i < len - n - 1; i++) t = t.next;   // t is now the node just before the target
    t.next = t.next.next;
    return head;
}

Complexity. Time O(len): one counting pass and one partial pass. Space O(1).

Two passes is already linear and perfectly acceptable; the follow-up is about doing it in one.

Approach 2: Optimal, two pointers a fixed gap apart

Intuition. Place two pointers n nodes apart and move them forward together. When the front pointer reaches the last node, the back pointer is exactly n nodes behind it, so it sits on the node before the one we must delete. We never need to know len.

Concretely, advance fast by n steps first. If that makes fast null, then the gap is the whole list and the target is the head. Otherwise walk slow (from head) and fast together until fast.next is null; slow.next is the target.

Algorithm.

1. If n ≤ 0, return head.
2. Move fast forward n times; if it becomes null before completing the n steps, n exceeds the length, so return head.
3. If fast is null right after the n steps, the target is the head: return head.next.
4. Set slow = head. While fast.next != null, advance both.
5. Set slow.next = slow.next.next and return head.

static ListNode optimal(ListNode head, int n) {
    if (n <= 0) return head;
    ListNode fast = head;
    for (int i = 0; i < n; i++) {
        if (fast == null) return head;           // n is larger than the length: nothing to remove
        fast = fast.next;
    }
    if (fast == null) return head.next;          // the gap spans the whole list, so the head is the target
    ListNode slow = head;
    while (fast.next != null) {                  // stop when fast stands on the last node
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;                  // unlink the target
    return head;
}

Dry run on 1 -> 2 -> 3 -> 4 -> 5, n = 2:

For n = 5 the first phase moves fast five times: 2, 3, 4, 5, null. It ends null, so the method returns head.next = 2 -> 3 -> 4 -> 5.

Complexity. Time O(len): fast visits each node once, and slow visits a prefix. Space O(1): two pointers.

Both approaches are checked against an array-based reference answer in the Java file, including removal of the head, the tail, the only node, and n values that are too large or zero.

A popular alternative formulation puts a dummy node in front of head, starts both pointers on the dummy, and then never needs the “is the target the head?” branch, because even the head has a predecessor. The gap logic is otherwise identical: move fast forward n + 1 times from the dummy, walk both until fast is null, and unlink slow.next. The version above checks the head case explicitly instead, which keeps the method free of allocation and makes the three outcomes (head removed, interior node removed, nothing removed) visible as separate returns. Either style is acceptable in an interview; what matters is being able to say why the back pointer ends up on the predecessor rather than on the target itself.

Edge cases and pitfalls

• Removing the head. The head has no predecessor. Detect it explicitly (n == len, or fast == null after n steps) and return head.next. A dummy node in front of head is another standard way to avoid this case; the code here checks directly instead.
• Single node, n = 1. Falls under “remove the head” and returns null.
• Removing the tail, n = 1. The walking phase stops when fast is on the tail; slow is the second-to-last node and slow.next = null drops the tail.
• n larger than the length. Walking fast forward hits null early. The code returns the list unchanged rather than throwing; LeetCode guarantees this never happens, but a defensive check costs nothing.
• n = 0 or negative. Without a guard, fast would not move and the loop would run slow to the tail and then dereference null. Both methods return early.
• Off-by-one in the gap. Stopping when fast == null instead of fast.next == null lands slow on the target instead of before it, and a singly linked node cannot delete itself.
• Counting mistakes in the brute force. The predecessor is at index len - n - 1; walking len - n steps deletes the wrong node.

Related problems

• Delete the middle node in LL uses the same “stop one node before the target” idea with slow and fast pointers.
• Deletion of the head of LL covers the special case where the target has no predecessor.
• Find the length of the Linked List is the counting pass used by the brute force.
• Rotate a LL also locates a node a fixed distance from the end.