LeetCode. 19. Remove Nth Node From End of List

[Link] https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Given the head of a singly linked list, remove its nth node from the end and return the head. The input guarantees that n is valid. Relink the existing nodes rather than copying their values.

Use a dummy node before the head and two pointers, fast and slow. First advance fast by n links from the dummy, so the pointers have an n-node gap. Then move both pointers together until fast is the last node. At that point, slow is immediately before the node to remove; unlink it by assigning slow.next = slow.next.next.

The dummy node supplies a predecessor even when the node to remove is the original head. Thus head removal uses the same unlinking step as every other position, and dummy.next is the resulting head. Since n is guaranteed valid, advancing fast by n links is safe.

Time complexity is $O(N)$, and extra space complexity is $O(1)$.

/**
 * 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);
        ListNode fast = dummy;
        ListNode slow = dummy;

        // Keep fast n links ahead, then move both pointers in lockstep.
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // slow is the predecessor, including when the original head is removed.
        slow.next = slow.next.next;
        return dummy.next;
    }
}