Связные списки
Обмен узлов попарно
Поменять местами соседние узлы односвязного списка
Постановка задачи
Описание (LeetCode - 24. Swap Nodes in Pairs)
Дана голова односвязного списка head.
Нужно поменять местами каждые два соседних узла и вернуть голову измененного списка.
Менять значения в узлах нельзя. Нужно менять сами узлы.
Пример 1:
head = [1, 2, 3, 4]
Результат:
[2, 1, 4, 3]
Пример 2:
head = []
Результат:
[]
Пример 3:
head = [1]
Результат:
[1]
Ограничения:
- Количество узлов в списке от
0до100 0 <= Node.val <= 100
Решение
На первый взгляд кажется, что можно просто поменять значения внутри соседних
узлов. Но условие запрещает это делать: нужно переставить именно узлы, то есть
поменять ссылки next.
Идея решения:
Будем обрабатывать список парами. Для каждой пары нам нужен указатель на узел
перед этой парой. Назовем его previous.
Если текущая пара выглядит так:
previous -> first -> second -> nextPair
После обмена она должна выглядеть так:
previous -> second -> first -> nextPair
Перейдите на Premium, чтобы продолжить
Разблокируйте доступ к этой статье и всем остальным материалам с NowInterview Premium
Перейти на Premium