Как найти k-й элемент с конца в односвязном списке за один проход?

Эффективный алгоритм использует метод двух указателей (runner technique). Он решает задачу за один проход по списку с константной памятью O(1).

Алгоритм:

1. Инициализируем два указателя: fast (быстрый) и slow (медленный), оба указывают на голову списка.
2. Сначала перемещаем fast на k узлов вперед. Это создает "разрыв" в k узлов между указателями.
3. Затем перемещаем оба указателя одновременно по одному узлу за шаг, пока fast не достигнет конца списка (null).
4. В этот момент slow будет указывать именно на k-й элемент с конца (или на null, если k больше длины списка).

Визуализация для k=2 и списка [1->2->3->4->5]:

Шаг 1 (fast ушел на 2 узла): slow=1, fast=3
Шаг 2: slow=2, fast=4
Шаг 3: slow=3, fast=5
Шаг 4: slow=4, fast=null -> STOP. Ответ = 4.

Реализация на C#:

public class ListNode {
    public int Value { get; set; }
    public ListNode Next { get; set; }
}

public ListNode FindKthFromEnd(ListNode head, int k) {
    if (head == null || k <= 0) return null;

    ListNode fast = head;
    ListNode slow = head;

    // 1. Перемещаем fast на k узлов вперед
    for (int i = 0; i < k; i++) {
        if (fast == null) {
            // Если k больше длины списка, возвращаем null
            return null;
        }
        fast = fast.Next;
    }

    // 2. Двигаем оба указателя, пока fast не достигнет конца
    while (fast != null) {
        slow = slow.Next;
        fast = fast.Next;
    }

    // 3. slow теперь указывает на k-й элемент с конца
    return slow;
}

Сложность:

• Время: O(n), где n — длина списка. Список проходит только один раз.
• Память: O(1), дополнительная память не зависит от размера списка.

Альтернативы и их недостатки:

• Два прохода: Сначала найти длину n, затем пройти до (n-k)-го элемента. Сложность тоже O(n), но требует двух проходов.
• Стек: Помещать все узлы в стек, затем выталкивать k элементов. Требует O(n) дополнительной памяти.