Crack the Backend

Problem Statement

Given the head of a linked list, remove the n-th node from the end of the list and return its head. Assume n is valid (1-indexed from the end). Try to do this in one pass.

The n-th node from the end is the node such that there are n-1 nodes after it. So we need to find the node at position (length - n) from the start (0-indexed) and remove it.
Using a dummy node before head simplifies the case when we remove the head (n = length).

Key Observations

Two pointers with gap: Place fast and slow so that fast is n+1 steps ahead of slow. When fast reaches null (past the last node), slow is at the node before the one to remove. So we set slow.next = slow.next.next.
Use a dummy node: dummy.next = head. Start fast = dummy and move fast forward n+1 times (so the gap between slow and fast is n+1 when slow = dummy). Then move both until fast == null. slow.next is the n-th from the end; remove it.

Approach

High-level: Dummy node before head. Move fast from dummy forward n+1 times. Then move slow and fast together until fast == null. slow is the predecessor of the node to remove; set slow.next = slow.next.next. Return dummy.next.

Steps:

ListNode dummy = new ListNode(0); dummy.next = head; fast = dummy; move fast forward n+1 times (for loop).
slow = dummy. While fast != null: fast = fast.next, slow = slow.next.
slow.next = slow.next.next. Return dummy.next.

Implementation

Java

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy, slow = dummy;

    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 dummy.next;
}

Test Cases

Example 1

Input

head = [1,2,3,4,5], n = 2

Expected

[1,2,3,5]

Explanation

Remove 4.

Complexity Analysis

Time: O(n).
Space: O(1).

Follow-ups

One pass without dummy: handle n==length separately.