Манипуляция указателями на связных списках

Основная проблема: связывание и отсоединение

Чтобы вставить или удалить узел в связном списке, ты должен внимательно обновить указатели. Это не про создание или удаление узлов в памяти (это работа аллокатора); это про изменение того, на что указывает next.

Вставка: операция splice

Представь связный список [10] → [20] → [30] и ты хочешь вставить 15 между 10 и 20.

Чтобы вставить узел после данного узла:

1. Создай новый узел (15).
2. Установи next нового узла на старого наследника (20).
3. Установи next данного узла на новый узел (15).

Это “splice” — ты разломал ссылку 10 → 20, вставил 15 посередине, и пересобрал цепь: 10 → 15 → 20.

Раньше:  [10 | next → ] → [20 | next → ] → [30 | null]

После:   [10 | next → ] → [15 | next → ] → [20 | next → ] → [30 | null]
                            ↑ вновь вставлен

Операция это O(1) по времени потому что ты только изменяешь указатели; ты не проходишь список. Но ты должен иметь ссылку на узел перед точкой вставки. Если ты хочешь вставить на позицию i (и у тебя есть только head), ты сначала проходишь на позицию i-1, что стоит O(i) времени всего.

Удаление: операция отсоединения

Теперь удали 15 из [10] → [15] → [20] → [30].

Чтобы удалить узел, ты нуждаешься в ссылке на узел перед ним. Тогда:

1. Установи next предыдущего узла чтобы пропустить цель, указывая прямо на наследника цели.

Раньше:  [10 | next → ] → [15 | next → ] → [20 | next → ] → [30 | null]

После:   [10 | next → ] ─────────────────> [20 | next → ] → [30 | null]
                        (15 теперь недостижим)

Время: O(1) удалить если у тебя есть ссылка на предыдущий узел. O(i) если ты должен сначала пройти чтобы найти.

Граничный случай с head: почему dummy heads важны

Вставка и удаление легко если цель в середине. Но что если ты хочешь вставить в head или удалить head? Тогда нет “предыдущего узла”. Это заставляет тебя писать специальные случаи:

if (insertingAtHead) {
  // Специальный случай: создай новый head
  const newNode = new Node(value);
  newNode.next = head;
  head = newNode;
} else {
  // Нормальный случай: вставь после какого-то узла
  const prev = findNodeBefore(position);
  const newNode = new Node(value);
  newNode.next = prev.next;
  prev.next = newNode;
}

Это дублирование уродливо. Хитрость: представь dummy узел.

Паттерн dummy head (sentinel node)

Создай специальный узел, dummy head, что всегда указывает на настоящий head. Этот dummy не часть твоих данных; это просто якорь.

Dummy (0) → [10 | next → ] → [20 | next → ] → [30 | null]
   ↑
 Всегда существует; действует как предыдущий узел для вставок в настоящий head

Теперь каждая операция имеет “предыдущий узел” — либо настоящий узел либо dummy. Вставка и удаление используют одинаковую логику везде:

// Нет специальных случаев нужно
const newNode = new Node(value);
newNode.next = prev.next;  // prev может быть dummy
prev.next = newNode;

Преимущества:

1. Единая логика. Одна вставка/удаление логика работает для head и середины.
2. Более чистые удаления. Даже если ты удалишь head, dummy всё ещё указывает на новый head.
3. Безопаснее. Ты исключаешь проверки на null-указатель для “есть ли предыдущий узел?”
4. Легче кодировать правильно. Меньше граничных случаев = меньше багов.

Разворот: развораживание всех указателей

Развёртывание [10] → [20] → [30] → [null] в [30] → [20] → [10] → [null] означает изменение каждого next указателя чтобы он указывал назад.

Один подход: итерируй по списку, и в каждом узле разверни его указатель.

Шаг 0: prev = null,  current = 10 → 20 → 30
        next = 20 (сохрани это перед тем как мы изменим current.next)
        
Шаг 1: prev = 10 ← null (мы развернули это),  current = 20 → 30
        next = 30 (сохрани это)
        
Шаг 2: prev = 20 ← 10,  current = 30 → null
        next = null (сохрани это)
        
Шаг 3: prev = 30 ← 20,  current = null (готово)

Результат: prev указывает на новый head (30).

Ключевая идея: сохрани next указатель перед тем как ты его перезапишешь. Иначе ты теряешь ссылку и не можешь продолжить.

let prev = null;
let current = head;

while (current !== null) {
  const next = current.next;  // Сохрани следующий узел
  current.next = prev;        // Разверни указатель
  prev = current;             // Продвинься вперёд
  current = next;
}

head = prev;  // Новый head это последний узел что мы обработали

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