Паттерн: Связный список

Признак в условии

• узлы { value, next }, произвольного доступа по индексу нет
• «развернуть», «найти середину», «есть ли цикл», «n-й с конца»
• требуется O(1) дополнительной памяти

Приёмы

Три указателя для разворота: сохранить next → переписать ссылку → сдвинуть оба. Быстрый и медленный: fast делает два шага, slow один - середина и поиск цикла. Фиктивная голова: избавляет от особого случая «меняем первый элемент».

Шаблон

let prev = null, cur = head;
while (cur) {
  const next = cur.next;   // сохранить ДО перезаписи
  cur.next = prev;
  prev = cur;
  cur = next;
}
return prev;               // возвращаем prev, а не cur

const dummy = { next: head };   // фиктивная голова
let slow = dummy, fast = dummy;

Сложность

Время O(n), память O(1).

Частые ошибки

• cur.next переписан до сохранения next - хвост потерян
• возвращают cur (он уже null) вместо prev
• удаление головы не обработано - лечится фиктивным узлом
• в цикле поиска середины проверяют только fast, забывая fast.next

Мнемоника

«Сохрани, переверни, сдвинь»

Не путать с

• Два указателя - быстрый и медленный - это два указателя; отличие в том, что длину заранее не знаешь и назад не ходишь
• Стек - если нужно пройти список задом наперёд, а память не жалко, проще сложить в стек, чем разворачивать

Задачи на этот паттерн

• разворот связного списка
• середина списка
• слияние отсортированных списков
• удалить n-й с конца
• цикл в списке
• список-палиндром
• сложение чисел списками
• перестановка по чётности позиций

Суть

Связный список это цепочка узлов { val, next }. Нет доступа по индексу (O(n)), зато вставка и удаление в известном месте O(1). На собесе списки проверяют аккуратность с указателями.

class ListNode {
  constructor(val, next = null) { this.val = val; this.next = next; }
}

Как распознать по условию

Тут проще: задача прямо говорит «дан связный список». Дальше выбираешь приём:

• развернуть (весь, часть, группами) → три указателя;
• середина, цикл, k-й с конца → быстрый и медленный указатели;
• слияние, удаление по условию → фиктивный узел dummy;
• палиндром → середина + разворот второй половины.

Разворот

function reverse(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next; // сохранить хвост
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

Быстрый и медленный

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Тот же цикл без проверки встречи находит середину: когда fast дошёл до конца, slow посередине.

Фиктивный узел

function removeAll(head, x) {
  const dummy = new ListNode(0, head);
  let p = dummy;
  while (p.next) {
    if (p.next.val === x) p.next = p.next.next;
    else p = p.next;
  }
  return dummy.next;
}

Сложность

Почти всё O(n) времени и O(1) памяти. Рекурсивные решения тратят O(n) стека.

Ловушки

• Перевесить next до того, как сохранил его: потеря хвоста.
• fast.next.next без проверки fast.next: TypeError.
• Отдельная ветка для головы вместо dummy.
• Забыть обнулить next у нового хвоста: цикл.
• Сравнивать узлы по val, а не по ссылке, при поиске цикла или пересечения.

Что спросят на собесе

• Разверни список итеративно и объясни память.
• Как найти цикл за O(1) памяти?
• Удали k-й узел с конца за один проход.
• Слей два отсортированных списка.
• Чем список лучше и хуже массива?