Палиндромный связный список

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

head = [1, 2, 2, 1]

true

head = [1, 2]

false

Решение

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

Можно скопировать все значения в массив и проверить палиндром на массиве. Это работает за O(n), но требует O(n) дополнительной памяти.

Оптимальный способ - решить задачу на месте за O(1) памяти.

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

Нам нужно сравнить первую половину списка со второй половиной в обратном порядке:

1. Находим середину списка быстрым и медленным указателями (Середина связного списка).
2. Разворачиваем вторую половину списка (Разворот списка).
3. Сравниваем значения в первой и развернутой второй половине.

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

1. Инициализация: slow и fast стоят на голове списка.

2. Двигаем slow на один шаг, fast на два.

3. fast доходит до конца. slow указывает на начало второй половины (на узел 2).

4. Разворачиваем вторую половину и сравниваем значения первой и развернутой второй части.

5. Все значения совпадают, список является палиндромом.

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

1. Инициализация: оба указателя на голове.

2. slow останавливается на среднем узле 3.

3. Разворачиваем вторую половину от узла 3. Сравнение идет, пока не закончится развернутая часть. Средний элемент сравнивается сам с собой и не мешает проверке.

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

1. Инициализируем slow = head, fast = head.
2. Двигаем slow на один шаг, а fast на два шага, пока fast != null и fast.next != null.
3. Разворачиваем вторую половину списка, начиная с slow.
4. Сравниваем значения от head и от головы развернутой части.
5. Если значения в узлах не совпадают, возвращаем false.
6. Если развернутая часть закончилась, возвращаем true.

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

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

Мы один раз ищем середину списка, один раз разворачиваем вторую половину и один раз сравниваем половины. Каждая операция линейна.

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

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

Мы используем только несколько указателей и разворачиваем список на месте.

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

Код решения

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

func isPalindrome(head *ListNode) bool {
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
 
    second := reverseList(slow)
    first := head
    for second != nil {
        if first.Val != second.Val {
            return false
        }
        first = first.Next
        second = second.Next
    }
    return true
}
 
func reverseList(head *ListNode) *ListNode {
    var previous *ListNode
    current := head
    for current != nil {
        next := current.Next
        current.Next = previous
        previous = current
        current = next
    }
    return previous
}

Итоги

Задача Palindrome Linked List показывает, как использовать паттерн быстрого и медленного указателей вместе с разворотом списка, чтобы избежать выделения дополнительного массива.

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