Topics › Linked List › Medium Problems of LL

Remove Nth node from the back of the LL

Medium TUF ID 626 SDEBlind 75

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 of the list and return the head of the resulting list. n = 1 means the tail and n = len means the head. The follow-up asks you to do it in a single pass.

Constraints: 1 ≤ len ≤ 30 in the LeetCode version, 1 ≤ n ≤ len, values fit in an int. The Java solutions also leave the list unchanged when n is out of range (zero, negative or larger than the length), 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 node from the end is 4

Example 2

head = 1, n = 1
answer = (empty)                 // the only node is removed

Example 3

head = 1 -> 2, n = 2
answer = 2                       // the 2nd from the end is the head itself

The key translation: the n-th node from the end has 0-based index len - n from the front. To unlink it in a singly linked list you must stand on its predecessor, index len - n - 1, and set prev.next = prev.next.next. Every approach below is a different way of reaching that predecessor, plus some care for the case where there is no predecessor because the target is the head.

Approach 1: Brute force, two passes

Intuition. You cannot count backwards in a singly linked list, so convert “from the end” into “from the front”. One pass counts the nodes. With len known, the predecessor is len - n - 1 steps from the head, and a second pass walks there. If n == len, the target is the head, which has no predecessor; the new head is simply head.next.

Algorithm.

1. Count the nodes into len. If n is not in 1..len, return the list unchanged.
2. If n == len, return head.next.
3. Walk len - n - 1 steps from the head to reach prev.
4. Set prev.next = prev.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;          // out of range: leave the list alone
    if (n == len) return head.next;              // the target is the head itself
    ListNode prev = head;
    for (int i = 0; i < len - n - 1; i++) prev = prev.next;   // prev is now just before the target
    prev.next = prev.next.next;
    return head;
}

Complexity. Time O(len): one full pass plus at most one more. Space O(1).

This is already linear, but it reads the list twice. The follow-up asks for one pass, which forces you to find the predecessor without knowing the length in advance.

Approach 2: Better, one pass with node references

Intuition. The second pass exists only because a linked list has no random access. If, during the first pass, you remember a reference to every node in an ArrayList, then after that pass you can jump straight to index len - n - 1. This genuinely reads the list once, at the price of memory proportional to its length.

Algorithm.

1. Walk the list, adding each node to nodes.
2. If n is out of range, return the head unchanged.
3. Let target = len - n. If target == 0, return head.next.
4. Otherwise set nodes.get(target - 1).next = nodes.get(target).next and return the head.

static ListNode better(ListNode head, int n) {
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode t = head; t != null; t = t.next) nodes.add(t);
    int len = nodes.size();
    if (n <= 0 || n > len) return head;
    int target = len - n;                        // 0-based index of the node to delete
    if (target == 0) return head.next;
    nodes.get(target - 1).next = nodes.get(target).next;
    return head;
}

Complexity. Time O(len), one pass. Space O(len) for the array of references. The extra memory is the reason this is not the final answer.

Approach 3: Optimal, two pointers with a gap of n

Intuition. Picture a rigid stick of length n laid along the list. If the front end of the stick sits on the last node, the back end sits exactly n nodes earlier, which is the predecessor of the n-th node from the end. You do not need to know the length to place the stick: first move a fast pointer n nodes ahead of a slow pointer, then slide both forward together until fast reaches the last node. The gap never changes, so when fast is on the last node, slow is on the predecessor.

Why exactly the predecessor: put a dummy node in front of the head and call its index -1. After the gap phase fast is at index n - 1 and slow at -1. Sliding both until fast reaches index len - 1 moves them len - n steps, leaving slow at index len - n - 1, the predecessor of index len - n.

The dummy node is what removes the special case. When the target is the head, its predecessor is the dummy, and the same slow.next = slow.next.next line unlinks it. Returning dummy.next then gives the correct new head in every case.

Algorithm.

1. If n <= 0, return the head unchanged.
2. Create dummy with dummy.next = head, and set fast = slow = dummy.
3. Move fast forward n times. If it falls off the list, n is larger than the length; return the head unchanged.
4. While fast.next != null, move both pointers one step.
5. Set slow.next = slow.next.next and return dummy.next.

static ListNode optimal(ListNode head, int n) {
    if (n <= 0) return head;
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
        if (fast == null) return head;           // n is larger than the length
    }
    while (fast.next != null) {                  // stop when fast stands on the last node
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;                  // slow is just before the target
    return dummy.next;                           // the head may have been the target
}

Dry run on 1 -> 2 -> 3 -> 4 -> 5, n = 2 (D is the dummy):

The result is 1 -> 2 -> 3 -> 5. With n = 5 the gap phase leaves fast on node 5, no slide happens, slow is still the dummy, and unlinking dummy.next removes the head.

Complexity. Time O(len): fast visits each node once, and slow trails it. Space O(1): the dummy node and two pointers.

Edge cases and pitfalls

• Removing the head (n == len). This is the case most bugs hide in. The brute force and the array version return head.next explicitly; the optimal version handles it through the dummy node. Returning head instead of dummy.next would leave the deleted node in place.
• Single node. 1 with n = 1 must become an empty list, which is just the head-removal case.
• Removing the tail (n = 1). slow ends on the second-to-last node and its next becomes null.
• Out-of-range n. LeetCode guarantees 1 ≤ n ≤ len, but defensive code should not throw. All three methods return the list unchanged when n is zero, negative or larger than the length; the optimal version detects this when fast becomes null during the gap phase.
• Off-by-one in the slide loop. Stop when fast.next == null (fast on the last node), not when fast == null. The second condition moves slow one step too far, onto the target itself, and you cannot unlink a node while standing on it.
• Duplicate values. Position decides, not value. 7 -> 7 -> 7 -> 7 with n = 3 must remove the second node.

Related problems

• Remove Nth node from the back of the LL is the same problem as it appears in the A2Z sheet.
• Find Middle of Linked List uses two pointers at different speeds instead of a fixed gap.
• Rotate a LL also needs the node k positions from the end.
• Delete the middle node in LL is another “stand on the predecessor and unlink” problem.
• Delete Node in a Linked List O(1) shows what to do when you cannot reach the predecessor at all.