Быстрый и медленный указатели
Переупорядочить список
Переставить узлы списка в порядке L0, Ln, L1, Ln-1
Постановка задачи
Описание (LeetCode - 143. Reorder List)
Дана голова односвязного списка head.
Нужно изменить список на месте так, чтобы порядок узлов стал следующим:
L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...
Нельзя менять значения в узлах. Нужно переставлять сами узлы.
Пример 1:
head = [1, 2, 3, 4]
После изменения:
[1, 4, 2, 3]
Пример 2:
head = [1, 2, 3, 4, 5]
После изменения:
[1, 5, 2, 4, 3]
Ограничения:
- Количество узлов в списке от
1до5 * 10⁴ 1 <= Node.val <= 1000
Решение
Если бы значения можно было менять, мы могли бы скопировать их в массив и перезаписать в нужном порядке. Но условие запрещает менять значения: нужно переставлять сами узлы.
В односвязном списке нет быстрого доступа к хвосту и предыдущим узлам за O(1).
Поэтому напрямую брать узлы Ln, Ln-1, Ln-2 неудобно.
Задачу можно разложить на три знакомых шага:
Перейдите на Premium, чтобы продолжить
Разблокируйте доступ к этой статье и всем остальным материалам с NowInterview Premium
Перейти на Premium