38.Remove Nth Node From End of List

MediumBlind 75Linked List · 4/11

Problem

Given the head of a linked list, remove the n-th node from the end of the list and return the head of the modified list.

n is always valid (1 <= n <= length). Note that if n equals the length, the node to remove is the head itself.

Examples

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

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

Input:  head = [1, 2], n = 1
Output: [1]

Constraints

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

💡 Key Insight

To delete a node in a singly linked list you need the node before it. If two pointers start together and the fast one is moved n + 1 steps ahead, then when fast falls off the end, slow sits exactly one node before the target — giving a single pass. A dummy node before head makes removing the head itself no different from any other removal.

Brute Force (Array of Nodes)

TimeO(L)SpaceO(L)

Intuition

Linked lists lack random access, so copy the node references into an array. Then the target is at index size - n and its predecessor at size - n - 1.

Algorithm

Collect every node into nodes.
idx = size - n is the node to remove.
If idx == 0, return head.next (removing the head).
Otherwise nodes[idx - 1].next = nodes[idx].next and return head.

Visualization

nodes: [1, 2, 3, 4, 5], n = 2
idx = 5 - 2 = 3  -> node 4
nodes[2] (3).next = nodes[3].next (5)
result: 1 -> 2 -> 3 -> 5

Code

java

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) {
            nodes.add(node);
        }
        int idx = nodes.size() - n; // index of the node to delete
        if (idx == 0) {
            return head.next; // deleting the head
        }
        nodes.get(idx - 1).next = nodes.get(idx).next;
        return head;
    }
}

Complexity

Time: O(L) — one pass over the L nodes.
Space: O(L) — the array of references.

Two Passes (Count Length)

TimeO(L)SpaceO(1)

Intuition

Without storing nodes, first count the length L. The node to delete is at position L - n (0-indexed), so its predecessor is reached by walking L - n steps from a dummy node.

Algorithm

Count length.
Create dummy with dummy.next = head; set prev = dummy.
Move prev forward length - n times.
prev.next = prev.next.next.
Return dummy.next.

Visualization

dummy -> 1 -> 2 -> 3 -> 4 -> 5,  length = 5, n = 2
walk 5 - 2 = 3 steps from dummy: prev = 3
3.next = 3.next.next  (skip 4)

Code

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = 0;
        for (ListNode node = head; node != null; node = node.next) {
            length++;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        for (int i = 0; i < length - n; i++) {
            prev = prev.next; // stop right before the target
        }
        prev.next = prev.next.next;
        return dummy.next;
    }
}

Complexity

Time: O(L) — two passes over the list.
Space: O(1) — a counter and a few pointers.

One Pass with Two PointersOptimal

TimeO(L)SpaceO(1)

Intuition

Keep a fixed gap of n nodes between two pointers. Start both at dummy, move fast ahead n + 1 steps, then move both together until fast is null. Since the gap never changes, slow ends exactly one node before the n-th node from the end.

Algorithm

dummy.next = head; slow = fast = dummy.
Move fast forward n + 1 times.
While fast != null: advance both slow and fast.
slow.next = slow.next.next.
Return dummy.next.

Dry Run

flowchart TD
    A["dummy -> 1 -> 2 -> 3 -> 4 -> 5, n = 2<br/>slow = dummy, fast = dummy"] -->|"move fast n+1 = 3 steps"| B["slow = dummy, fast = 3"]
    B -->|"move both"| C["slow = 1, fast = 4"]
    C -->|"move both"| D["slow = 2, fast = 5"]
    D -->|"move both"| E["slow = 3, fast = null"]
    E -->|"slow.next = slow.next.next"| F["1 -> 2 -> 3 -> 5"]

Code

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head); // handles removing the head
        ListNode slow = dummy, fast = dummy;
        for (int i = 0; i <= n; i++) {
            fast = fast.next; // create a gap of n nodes between slow and fast
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next; // skip the target node
        return dummy.next;
    }
}

Complexity

Time: O(L) — fast traverses the list once.
Space: O(1) — two pointers and a dummy node.

Complexity Comparison

Approach	Time	Space
Array of Nodes	O(L)	O(L)
Two Passes	O(L)	O(1)
One Pass Two Pointers	O(L)	O(1)

Common Pitfalls

Not using a dummy node, then crashing (or returning the wrong head) when n equals the list length and the head must be removed.
Moving fast only n steps instead of n + 1 from the dummy — slow then lands on the target instead of its predecessor.
Returning head instead of dummy.next — if the head was deleted, head is stale.
Off-by-one in the two-pass version: the predecessor is length - n steps from the dummy, not from head.