Подготовка к алгоритмическим задачам

Разворот односвязного списка: разбор задачи

7 мин чтения

алгоритмы

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

рекурсия

Почему эта задача важна?

Задача на разворот односвязного списка позволяет оценить:

🧠 Понимание принципов работы со связными структурами данных
⚡ Навыки манипуляции указателями и ссылками
🎯 Умение мыслить последовательно при трансформации данных
🔄 Способность применять как итеративные, так и рекурсивные подходы

Постановка задачи

Формулировка:

Дан односвязный список head. Разверните список и верните новый его начало.

Примеры:

// Первый пример ✅
Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

// Второй пример ✅
Input: head = [1, 2]
Output: [2, 1]

// Третий пример ✅
Input: head = []
Output: []

Ограничения:

Длина списка: 0 <= длина <= 1000
Значение узла: -1000 <= Node.val <= 1000

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к решению

Решение 1: Итеративный подход 🔄

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
function reverseList(head) {
  let prev = null;
  let current = head;
  
  while (current !== null) {
    // Сохраняем ссылку на следующий узел
    const next = current.next;
    
    // Меняем указатель текущего узла
    current.next = prev;
    
    // Перемещаем указатели prev и current вперед
    prev = current;
    current = next;
  }
  
  // В конце prev будет указывать на новую голову списка
  return prev;
}

Анализ решения:

✅ Оптимальная временная сложность O(n)

✅ Пространственная сложность O(1) - не требует дополнительной памяти

✅ Простая и понятная реализация

✅ Эффективно работает с большими списками

Решение 2: Рекурсивный подход 🌲

function reverseList(head) {
  // Базовый случай: пустой список или список из одного элемента
  if (head === null || head.next === null) {
    return head;
  }
  
  // Рекурсивно разворачиваем оставшуюся часть списка
  const newHead = reverseList(head.next);
  
  // Меняем направление связи между текущим узлом и следующим
  head.next.next = head;
  head.next = null;
  
  // Возвращаем новую голову списка
  return newHead;
}

Характеристики:

✅ Элегантная реализация

✅ Хорошо демонстрирует мощь рекурсии

❌ Пространственная сложность O(n) из-за стека вызовов

❌ Риск переполнения стека для больших списков

Решение 3: Итеративный подход с использованием массива 📚

function reverseList(head) {
  // Если список пуст или содержит один элемент
  if (head === null || head.next === null) {
    return head;
  }
  
  // Сохраняем все узлы в массиве
  const nodes = [];
  let current = head;
  
  while (current !== null) {
    nodes.push(current);
    current = current.next;
  }
  
  // Переворачиваем связи между узлами
  for (let i = nodes.length - 1; i > 0; i--) {
    nodes[i].next = nodes[i - 1];
  }
  
  // Последний узел (бывший первый) теперь указывает на null
  nodes[0].next = null;
  
  // Возвращаем новую голову списка
  return nodes[nodes.length - 1];
}

Преимущества и недостатки:

✅ Понятная логика решения

✅ Может быть проще для понимания новичками

❌ Требует дополнительной памяти O(n)

❌ Менее эффективен, чем итеративный подход

Решение 4: Разворот с использованием стека 📝

function reverseList(head) {
  // Если список пуст или содержит один элемент
  if (head === null || head.next === null) {
    return head;
  }
  
  // Используем стек для хранения узлов
  const stack = [];
  let current = head;
  
  // Помещаем все узлы в стек
  while (current !== null) {
    stack.push(current);
    current = current.next;
  }
  
  // Извлекаем узлы из стека и создаем новый список
  const newHead = stack.pop();
  current = newHead;
  
  while (stack.length > 0) {
    current.next = stack.pop();
    current = current.next;
  }
  
  // Не забываем обнулить ссылку у последнего элемента
  current.next = null;
  
  return newHead;
}

Особенности:

✅ Наглядно демонстрирует принцип "последний вошел, первый вышел"

✅ Хороший пример применения стека

❌ Требует дополнительной памяти O(n)

❌ Менее эффективен, чем прямой итеративный подход

Распространённые ошибки

🤦‍♂️ Потеря ссылок при развороте (создание циклов в списке)
😅 Забывание установить null для последнего элемента
🐛 Неправильная обработка пустого списка или списка из одного элемента

Оптимизации

In-place разворот с оптимизацией переменных

function reverseList(head) {
  if (!head || !head.next) return head;
  
  let [prev, current] = [null, head];
  
  while (current) {
    [current.next, prev, current] = [prev, current, current.next];
  }
  
  return prev;
}

Оптимизация рекурсии с помощью хвостовой рекурсии

function reverseList(head) {
  // Вспомогательная функция с дополнительными параметрами
  function reverse(current, prev = null) {
    if (current === null) {
      return prev; // Новая голова списка
    }
    
    const next = current.next;
    current.next = prev;
    
    // Хвостовая рекурсия позволяет оптимизировать использование стека
    return reverse(next, current);
  }
  
  return reverse(head);
}

Визуализация процесса

Рассмотрим разворот списка [1, 2, 3]:

Начальное состояние:
1 -> 2 -> 3 -> null

Шаг 1:
null <- 1    2 -> 3 -> null
      prev  curr  next

Шаг 2:
null <- 1 <- 2    3 -> null
           prev  curr  next

Шаг 3:
null <- 1 <- 2 <- 3
                 prev  curr=null

Результат:
3 -> 2 -> 1 -> null

Заключение

При решении задачи важно помнить:

🤹‍♂️ Существует несколько подходов с разными характеристиками по памяти и читаемости
📊 Итеративное решение обычно предпочтительнее по эффективности
🧠 Рекурсивное решение демонстрирует элегантный подход, но требует внимания к расходу памяти

Эта задача является классической при изучении связных списков и часто встречается на собеседованиях. Она отлично демонстрирует навыки работы с указателями и понимание принципов работы связных структур данных. 🌟

Попробуй решить популярные задачи

Массивы и Хеширование