Перейти на PRO

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

Тип вопроса: Алгоритмы и структуры данных Вероятность: 25% Категория: C# Разработчик

Ответ

Эффективный алгоритм использует метод двух указателей (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) дополнительной памяти.

Ответ 18+ 🔞

Ну ты смотри, какой прикол придумали, чтобы не ебаться с лишними проходами по списку! Есть такая штука — метод двух указателей, её ещё "бегунками" обзывают. Суть в том, что мы за один проход находим нужный элемент, и память при этом не жрёт, как не в себя — всего O(1), то есть константа, блядь.

Как это работает, на пальцах:

  1. Берём два указателя: fast (быстрый) и slow (медленный). Оба тыкаем в самый первый узел, в голову.
  2. Сначала гоняем нашего fast вперёд ровно на k шагов. Получается, между ними теперь дистанция в k узлов, как будто растянули резинку.
  3. А теперь начинаем двигать их синхронно, по одному шажку за раз. И так до тех пор, пока fast не упрётся в конец списка, в этот самый null.
  4. В этот самый момент наш slow будет как раз на том самом месте, где сидит k-й элемент с конца! Магия, ёпта! Если, конечно, k не больше, чем длина списка — тогда вернём null и не будем выёбываться.

Представь на примере, ищем второй с конца (k=2) в списке [1->2->3->4->5]:

Начинаем: slow=1, fast=1
Гоняем fast на 2 шага: slow=1, fast=3
Двигаем вместе: slow=2, fast=4
Ещё шаг: slow=3, fast=5
И последний: slow=4, fast=null -> СТОП! Вот он, наш ответ — четвёрка.

А вот как это в коде на 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 больше, чем узлов в списке
            return null;
        }
        fast = fast.Next;
    }

    // 2. Топаем вместе, пока fast не кончится
    while (fast != null) {
        slow = slow.Next;
        fast = fast.Next;
    }

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

Что по сложности?

  • По времени: O(n), потому что мы один раз пробегаемся по списку. Не два, не три, а один, что уже хорошо.
  • По памяти: O(1), потому что мы, кроме двух указателей, нихуя не храним. Никаких массивов, стеков и прочей хуйни.

А что, разве можно по-другому? Можно, конечно, но это будет или дольше, или память жрать. Например:

  • Два прохода: Сначала узнать длину списка n, потом пройти до элемента n-k. Тоже O(n), но бегать придётся дважды — не спортивно.
  • Запихнуть всё в стек: Толкаешь все узлы в стек, а потом вытаскиваешь k штук. Работает, но памяти сожрёт O(n), а это уже пиздец как расточительно для такой простой задачи.
© ХакСобесов, 2026
support@hacksobesov.com