Разворот списка

Сама по себе задача разворота связного списка, это то место на котором сыпятся 70% тех, кто пытается пройти собеседование в Google.
https://leetcode.com/problems/reverse-linked-list/description/

Элегантное выполнение разворота требует хорошего понимания того, как перемещать указатели, чего мы и постараемся достичь в этой статье.

Представьте, что у нас есть связный список 1 -> 2 -> 3 -> 4, и мы хотим вернуть 4 -> 3 -> 2 -> 1. Допустим, у нас есть указатель curr, представляющий текущий узел, на котором мы находимся. Начав с curr, указывающего на 1, нам нужно сделать так, чтобы 2 указывал на curr. Проблема в том, что как только мы перейдем к следующему узлу (curr = curr.next), чтобы добраться до 2, у нас больше не будет указателя на 1, так как это односвязный список. Чтобы решить эту проблему, мы можем использовать другой указатель prev, который будет отслеживать предыдущий узел.

На любом заданном узле curr мы можем установить curr.next = prev, чтобы изменить направление стрелки. Затем мы можем обновить prev, чтобы он указывал на curr, подготавливая его для следующего узла. Однако, если мы изменим curr.next, мы потеряем указатель на следующий узел. Чтобы это исправить, мы можем использовать временную переменную nextNode, чтобы указать на следующий узел перед изменением любых других указателей.

// Функция для разворота односвязного списка
let reverseList = (head) => {
  let prev = null; // Инициализируем предыдущий узел как null
  let curr = head; // Устанавливаем текущий узел на начало списка

  // Цикл продолжается, пока текущий узел не равен null
  while (curr) {
    let nextNode = curr.next; // Сохраняем следующий узел, чтобы не потерять его
    curr.next = prev; // Изменяем направление указателя текущего узла
    prev = curr; // Перемещаем указатель "предыдущего узла" на текущий узел
    curr = nextNode; // Переходим к следующему узлу
  }

  return prev; // Возвращаем новый "голову" развернутого списка
};

Объяснение

Инициализация указателей:
- prev изначально равен null, так как в развернутом списке последний узел должен указывать на null.
- curr устанавливается на head, чтобы начать проход по списку.
Сохранение следующего узла:
- Используем nextNode для хранения curr.next, чтобы не потерять ссылку на оставшуюся часть списка после изменения указателя.
Изменение указателя:
- Устанавливаем curr.next = prev, чтобы изменить направление текущего узла.
Перемещение указателей:
- Перемещаем prev на текущий узел (curr), а текущий узел (curr) на следующий узел (nextNode).
Возвращение новой головы:
- После завершения цикла указатель prev будет указывать на новый "голову" развернутого списка.

Сложность

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

Перестановка пар узлов в связном списке

https://leetcode.com/problems/swap-nodes-in-pairs/description/

Дано: связный список, например 1 -> 2 -> 3 -> 4 -> 5 -> 6. Нужно вернуть связный список, в котором каждая пара узлов меняется местами: 2 -> 1 -> 4 -> 3 -> 6 -> 5.

Подробный разбор

Представим, что первая пара узлов — это A -> B. Начнем с head, указывающего на узел A. Нам нужно, чтобы B указывал на A.

Шаги для выполнения

Перестановка узлов:
- Мы можем сделать так: head.next.next = head.
- Однако, если изменить B.next, мы потеряем доступ к оставшейся части списка.
Сохранение ссылки на следующий узел:
- До изменения, создаем указатель nextNode = head.next.next.
- head.next.next имеет разные значения в зависимости от того, стоит оно до или после оператора =:
  - До оператора = оно изменяет следующий узел.
  - После оператора = оно ссылается на следующий узел.
Переход к следующей паре:
- Сохраняем A в указателе prev = head (пока head все еще указывает на A).
- Перемещаемся к следующей паре, делая head = nextNode.
Соединение с остальной частью списка:
- После перемещения к следующей паре, например C -> D, нам нужно, чтобы A указывал на D.
- Это можно сделать так: prev.next = head.next.
Завершение текущей пары:
- После выполнения шагов 1-4, B указывает на A, а A указывает на D. Переходим к следующей паре.
Сохранение головы результата:
- Чтобы вернуть новый список, нам нужно сохранить B перед началом алгоритма, используя "фиктивный" узел (dummy).
Обработка нечетного числа узлов:
- Если узлов нечетное количество, последний узел останется нетронутым. В этом случае:
  - Устанавливаем head.next = nextNode перед шагом 4, чтобы сохранить ссылку.
Условие завершения:
- Цикл while работает, пока существуют оба узла head и head.next. Это гарантирует, что мы не попытаемся поменять местами последний одиночный узел.

Пример

Для списка A -> B -> C -> D:

После первой итерации: B -> A -> C -> D.
После второй итерации: B -> A -> D -> C.

Итоговый алгоритм

Выполнить перестановку узлов пары A -> B на B <-> A.
Сохранить ссылку на оставшуюся часть списка.
Соединить текущую пару с остальной частью списка.
Перейти к следующей паре и повторить.
Вернуть голову результата (узел B).

Сложность

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

Советы

Разбивайте задачу на шаги.
Используйте пример, чтобы отслеживать изменения.
При необходимости уточняйте детали на собеседовании.
Тщательно тестируйте крайние случаи, например:
- Нечетное количество узлов.
- Пустой список.
- Один узел.

Код

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  // Check edge case: linked list has 0 or 1 nodes, just return
  if (!head || !head.next) {
    return head;
  }

  let dummy = head.next; // Step 5
  let prev = null; // Initialize for step 3
  while (head && head.next) {
    if (prev) {
      prev.next = head.next; // Step 4
    }
    prev = head; // Step 3

    let nextNode = head.next.next; // Step 2
    head.next.next = head; // Step 1

    head.next = nextNode; // Step 6
    head = nextNode; // Move to next pair (Step 3)
  }

  return dummy;
};

Разворот как часть алгоритма

Мы упомянули, что разворот связного списка — это не только самостоятельная задача, но и техника, которая может использоваться как шаг для решения других задач. Давайте рассмотрим пример этого.

Пример: Максимальная сумма пар

Задача 2130. Maximum Twin Sum of a Linked List требует нахождения максимальной суммы пар узлов. Пары формируются следующим образом:

Первый и последний узел.
Второй и предпоследний узел.
Третий и третий с конца узел и так далее.

Решение

Простое решение:
- Конвертировать связный список в массив.
- Использовать индексацию для доступа к парам.
Элегантное решение с O(1) по памяти:
- Найти середину связного списка, используя технику быстрых и медленных указателей.
- Выполнить разворот второй половины списка.
- После разворота каждая пара узлов находится на расстоянии n / 2 друг от друга, где n — количество узлов.
- Создать указатель, который на n / 2 узлов впереди медленного указателя.
- Итеративно находить сумму пар slow.val + fast.val за n / 2 шагов от начала списка.

Важные моменты

В данном случае разворот списка — это не цель задачи, а лишь инструмент для оптимизации решения.
Использование быстрых и медленных указателей снова оказывается полезным.

Дополнительные применения связных списков

Хеширование и обработка коллизий:
- Техника цепочек (chaining) использует связные списки для обработки коллизий в хеш-таблицах.
Деки (deques):
- Структура данных, которая может быть реализована на основе связных списков.

Разворот списка

Объяснение​

Сложность​

Перестановка пар узлов в связном списке​

Подробный разбор​

Шаги для выполнения​

Пример​

Итоговый алгоритм​

Сложность​

Советы​

Код​

Разворот как часть алгоритма​

Пример: Максимальная сумма пар​

Решение​

Важные моменты​

Дополнительные применения связных списков​

Рекомендации​

Объяснение

Сложность

Перестановка пар узлов в связном списке

Подробный разбор

Шаги для выполнения

Пример

Итоговый алгоритм

Сложность

Советы

Код

Разворот как часть алгоритма

Пример: Максимальная сумма пар

Решение

Важные моменты

Дополнительные применения связных списков

Рекомендации