Связные списки

Связный список — цепочка узлов, где каждый узел хранит данные и указатель на следующий (и опционально на предыдущий в doubly-linked). Узлы могут быть разбросаны по памяти — связь поддерживается только через указатели. В отличие от массива даёт O(1) вставку/удаление в любом месте при наличии указателя на узел, но O(n) доступ по индексу. На собесах списки — это reverse, cycle detection, merge, k-th from end и LRU cache.

Когда применять / Мотивация

Связные списки нужны, когда:

• размер коллекции динамический и непредсказуемый (нет затрат на realloc как в массиве);
• частые вставки/удаления в середину при наличии указателя на позицию (O(1));
• структура должна позволять легко перемещать элементы — пример: LRU cache (doubly-linked list + hash map даёт O(1) на get/put).

В реальных системах списки встречаются:

• Ядра ОС: списки процессов, free-lists в memory allocator (malloc).
• Базы данных: hash chains для разрешения коллизий в hash bucket.
• Графы: adjacency lists — массив списков смежности.
• C++ STL: std::list — doubly-linked.
• Сборка мусора: free-lists в generational GC.

Кеш и реальность

В современных системах массивы часто быстрее списков даже для вставок: cache miss на каждом узле списка (узлы разбросаны по памяти) дороже, чем линейный сдвиг в массиве. Профилируйте, не доверяйте Big-O вслепую.

Идея / Как работает

Узел — объект с полями value и next (плюс prev для doubly-linked):

class ListNode<T> {
  value: T;
  next: ListNode<T> | null;
  constructor(value: T, next: ListNode<T> | null = null) {
    this.value = value;
    this.next = next;
  }
}

Вставка между A и B: создаём C, C.next = A.next; A.next = C; — O(1).

Удаление узла X: prev.next = X.next; — O(1) при наличии prev.

Доступ по индексу i: O(i) — идём с головы.

Память: каждый узел хранит указатели (~8 байт на x64), overhead 20–30% против массива. Кеш-локальность плохая — каждый переход потенциальный cache miss.

Ключевые техники

• Dummy head — фиктивный узел перед головой. Упрощает код, избавляя от проверок head === null.
• Fast/Slow pointers (черепаха и заяц) — slow на 1 шаг, fast на 2. Применяется для детекции циклов, поиска середины, n-го с конца.
• Сохранение next ДО перезаписи — иначе теряем хвост списка.

Реализация

Reverse Linked List (итеративно)

Задача: 1 → 2 → 3 → 4 → null превратить в 4 → 3 → 2 → 1 → null.

Идея: три указателя prev (хвост нового списка), curr (текущий узел), next (сохраняем перед перезаписью).

function reverseList(head: ListNode<number> | null): ListNode<number> | null {
  let prev: ListNode<number> | null = null;
  let curr = head;

  while (curr !== null) {
    const next = curr.next;  // сохраняем, чтобы не потерять хвост
    curr.next = prev;        // разворачиваем указатель
    prev = curr;             // сдвигаем prev
    curr = next;             // переходим дальше
  }
  return prev; // новая голова
}

Floyd’s Cycle Detection (детекция цикла)

function hasCycle(head: ListNode<number> | null): boolean {
  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 за O(n). Если нет — fast достигнет null.

Поиск середины списка

function findMiddle<T>(head: ListNode<T> | null): ListNode<T> | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow; // когда fast в конце, slow в середине
}

Merge двух отсортированных списков (с dummy head)

function mergeTwoLists(
  l1: ListNode<number> | null,
  l2: ListNode<number> | null,
): ListNode<number> | null {
  const dummy = new ListNode<number>(0);
  let tail = dummy;

  while (l1 && l2) {
    if (l1.value <= l2.value) { tail.next = l1; l1 = l1.next; }
    else                       { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 ?? l2; // присоединяем остаток
  return dummy.next;
}

Трассировка reverseList

head: 1→2→3→4→null, prev=null, curr=1
─────────────────────────────────────────
Шаг 1: next=2, curr.next=null → 1→null
       prev=1, curr=2
       состояние: prev: 1→null, остаток: 2→3→4→null
Шаг 2: next=3, curr.next=1 → 2→1
       prev=2, curr=3
       состояние: prev: 2→1→null, остаток: 3→4→null
Шаг 3: next=4, curr.next=2 → 3→2
       prev=3, curr=4
       состояние: prev: 3→2→1→null, остаток: 4→null
Шаг 4: next=null, curr.next=3 → 4→3
       prev=4, curr=null → выход
─────────────────────────────────────────
return prev = 4→3→2→1→null ✓

Инвариант цикла: prev — голова уже перевёрнутой части, curr — первый узел ещё не перевёрнутой части.

Сложность

Операция	Время	Память	Комментарий
Доступ по индексу	O(n)	O(1)	Идём с головы
Поиск значения	O(n)	O(1)	Линейный обход
Вставка после узла	O(1)	O(1)	Только указатели
Удаление известного узла	O(1)*	O(1)	* нужен prev (или doubly)
Reverse (итеративно)	O(n)	O(1)	3 указателя
Reverse (рекурсивно)	O(n)	O(n)	стек вызовов
Cycle detection (Floyd)	O(n)	O(1)	fast/slow
Merge two sorted	O(n+m)	O(1)	dummy head

Типичные ошибки и подводные камни

• Потеря ссылки: записать curr.next = prev без сохранения next = curr.next — потеряете весь хвост. Всегда сохраняйте перед перезаписью.
• Не обработать пустой список: head === null должно вернуть null. Большинство алгоритмов корректны, если цикл while не выполняется.
• Забыть про head/tail: при удалении головы нужен dummy head или специальный case.
• Цикл в списке: классический reverse зациклится навсегда — сначала проверьте через Floyd’s.
• Рекурсивный reverse: O(n) стек вызовов, при длинном списке (миллион узлов) — stack overflow. Итеративный надёжнее.
• Doubly-linked: при вставке/удалении не забыть обновить оба указателя — prev и next.
• JS gotcha: TypeScript не выводит non-null после if (curr) через несколько строк — нужен ! или явный narrowing.

Follow-up вопросы интервьюера

• Reverse рекурсивно. Доходим до конца, при возврате: curr.next.next = curr; curr.next = null;. O(n) времени, O(n) стека.
• Reverse part of list (left..right). Идём до left-1 (якорь), разворачиваем [left..right], склеиваем якорь с новой головой и хвост с right+1-узлом.
• Floyd’s: найти начало цикла. После встречи slow возвращаем в head, fast оставляем; двигаем оба по 1 шагу — точка встречи = вход в цикл (теорема Флойда).
• Reverse doubly-linked list. Меняем next и prev местами в каждом узле, обновляем head на бывший tail.
• Удалить n-й узел с конца за один проход. Two pointers: first идёт на n шагов вперёд, потом оба двигаются синхронно, пока first не достигнет конца. second окажется перед удаляемым.
• Merge K sorted lists. Min-heap из голов K списков: O(N log K), где N — суммарная длина.
• Copy List with Random Pointer. Hash map original → copy за два прохода или прошивка копий рядом с оригиналами за O(1) памяти.
• Palindrome Linked List. Найти середину, развернуть вторую половину, сравнить с первой. O(n) время, O(1) память.

Чеклист на собес

• Знаю шаблоны: dummy head, fast/slow, three pointers (reverse).
• Сохраняю next до модификации curr.next.
• Учитываю edge cases: пустой список, один узел, два узла.
• Помню Floyd’s для циклов и поиска середины.
• При doubly-linked обновляю оба указателя.
• Понимаю trade-off list vs array (cache miss vs O(1) вставка).
• Знаю, что итеративный reverse — O(1) памяти, рекурсивный — O(n).