Удалить n-й элемент с конца в односвязном списке

Задача. Дан односвязный список. Нужно удалить n-й элемент с конца и вернуть голову списка в качестве результата. Можно считать, что n <= размер списка.
Например:
Список: [1,2,3,4,5], n = 2 -> [1,2,3,5]
Список: [1], n = 1 -> []
Список: [1, 2], n = 2 -> [1]

Ссылка на leetcode: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
Решение.

Класс ноды (элемента списка):

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; 
    }
 }

Если бы список был двусвязным (когда у нас есть ссылка на следующий и предыдущий элемент в списке), то задача бы была намного проще. Мы бы начали итерироваться с конца списка и удалили бы n-й элемент. Но у нас список односвязный, у нас есть ссылка только на следующий элемент. Мы не можем итерировать с конца списка, только с начала.

Для решения применим метод, который называется Two Pointers (два указателя). Будем использовать одновременно два указателя для итерирования по списку. Первый назовем fast, второй slow.
Ключевая идея решения: вначале оба указателя указывают на начало списка. После отодвинем fast на n-элементов от slow (расстояние между fast и slow станет равным n). Далее будем одновременно двигать оба указателя, пока fast не достигнет конца списка. При этом slow будем указывать на n-й элемент с конца. Т.е. на тот элемент, который нам нужно удалить.
Посмотрим, как это будем работать на примере: [1, 2, 3, 4, 5], n = 2.

Отодвинем fast на 2 элемента от slow:

Далее будем одновременно двигать fast и slow, пока fast не достигнет конца списка. Также добавим указатель prev, который будет всегда указывать на предыдущий от slow элемент. Он нам понадобится для операции удаления:

После первой итерации состояние указателей будет таким:

Когда fast достигнет конца списка:

Теперь удаляем элемент, на который указывает индекс slow. Для этого меняем ссылку на следующий элемент для prev: prev.next = slow.next:

Посмотрим, как это будет работать для edge-case, когда нам надо удалить голову списка:

Отодвинем fast от slow на 2 элемента:

Далее будем одновременно двигать оба индекса, пока fast не достигнет конца списка. Но т.к. он уже в конце списка, то ничего двигать не надо. Надо просто удалить голову списка. При этом prev == null, поэтому удаление надо делать просто изменив указатель на начало списка: newHead = slow.next (или head = head.next):

Код решения:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;
        //Перемещаем fast указатель на расстояние n от slow
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        ListNode prev = null;
        //Итерируемся по списку до тех пор, пока fast не достигнет 
        //конца списка, а slow при этом будет указывать на n-й 
        //элемент с конца списка
        while (fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        //Edge-case, нужно удалить голову списка
        if (slow == head) {
            head = head.next;
            slow.next = null;
            return head;
        }
        // Удаляем n-й элемент списка с конца
        prev.next = slow.next;
        slow.next = null;
        return head;
    }
}