Premium

Быстрый и медленный указатели

Середина связного списка

Найти средний узел связного списка за один проход

Легкий

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

Описание (LeetCode - 876. Middle of the Linked List)

Дана голова односвязного списка head. Нужно вернуть средний узел списка.

Если средних узлов два, нужно вернуть второй из них.

Пример 1:

head = [1, 2, 3, 4, 5]

Результат:

[3, 4, 5]

Пояснение:

Средний узел имеет значение 3, поэтому возвращаем список начиная с этого узла: [3, 4, 5].

Пример 2:

head = [1, 2, 3, 4, 5, 6]

Результат:

[4, 5, 6]

Пояснение:

В списке два средних узла со значениями 3 и 4. По условию нужно вернуть второй из них, то есть узел со значением 4.

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

  • Количество узлов в списке от 1 до 100
  • 1 <= Node.val <= 100

Решение

Прямое решение - сначала посчитать длину списка за один проход, затем пройти еще раз до узла с индексом length / 2. Это работает, но требует двух проходов по списку.

Паттерн быстрого и медленного указателей позволяет найти середину за один проход.

Идея решения:

Запустим два указателя из головы списка:

  1. slow двигается на один узел за шаг.
  2. fast двигается на два узла за шаг.

Когда быстрый указатель дойдет до конца списка, медленный пройдет ровно половину пути и окажется на среднем узле.

Разберем на примере списка нечетной длины head = [1, 2, 3, 4, 5].

  1. Инициализация: slow и fast стоят на голове списка.
Инициализация
  1. Двигаем slow на один узел, fast на два (slow на 2, fast на 3).
slow +1, fast +2
  1. Двигаем еще раз: slow на 3, fast на 5. У fast.next значение null, цикл останавливается. slow указывает на середину списка.
slow на середине

Итог: узел со значением 3.

Для списка четной длины head = [1, 2, 3, 4, 5, 6]:

  1. Инициализация: оба указателя на голове списка.
Инициализация
  1. Первый шаг: slow на 2, fast на 3.
slow +1, fast +2
  1. Второй шаг: slow на 3, fast на 5.
slow на 3, fast на 5
  1. Третий шаг: fast переходит в null, а slow перемещается на 4. Цикл завершается, slow указывает на второй средний узел.
slow на втором среднем узле

Итог: узел со значением 4.

Основные шаги:

  1. Инициализируем slow = head, fast = head.
  2. Пока fast != null и fast.next != null:
    • двигаем slow на один шаг (slow = slow.next);
    • двигаем fast на два шага (fast = fast.next.next).
  3. Возвращаем slow.

Условие fast != null && fast.next != null гарантирует, что мы не обратимся к fast.next.next, когда следующего узла уже нет (как в списках четной, так и нечетной длины).

Оценка сложности

Временная сложность

Мы проходим по списку за один цикл. Быстрый указатель доходит до конца списка, а медленный проходит половину.

Итоговая временная сложность: O(n).

Пространственная сложность

Мы используем только два указателя.

Пространственная сложность: O(1).

Код решения

Приведем код решения.

func middleNode(head *ListNode) *ListNode {
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

Итоги

Задача Middle of the Linked List - классический пример использования паттерна быстрого и медленного указателей.

  1. Суть алгоритма: fast идет в два раза быстрее slow, поэтому к моменту достижения конца списка slow оказывается ровно в середине.
  2. Эффективность:
    • Временная сложность: O(n), так как список просматривается за один проход.
    • Пространственная сложность: O(1), используются только два указателя.
  3. Граничные случаи:
    • Один узел: он же является серединой.
    • Два узла: алгоритм корректно возвращает второй узел.
    • Нечетная длина: возвращается единственный средний узел.
    • Четная длина: условие остановки цикла приводит к возврату второго среднего узла.
  4. Оптимальное решение: мы не считаем длину списка отдельным проходом, а находим середину на лету.
Войдите чтобы отмечать прогресс