В этой задаче LeetCode нас просят создать функцию, которая берет LinkedList и меняет местами каждый из его элементов ListNode попарно. Другими словами, если значения LinkedList начинаются с [1, 2, 3, 4], наша функция должна изменить его на [2, 1, 4, 3].
Причина, по которой эта задача не является невероятно простой, заключается в том, как мы меняем местами ListNodes. В отличие от массивов, ListNodes требует обновления после замены, чтобы гарантировать правильность их .next указателей. Это значит, что для того, чтобы поменять местами 2 ListNodes, должно произойти следующее (обратите внимание, что когда я говорю «точка» в этих инструкциях, я имею в виду значение .next этого узла):
- Узел перед заменяемыми узлами должен указывать на узел 2
- Узел 2 теперь должен указывать на узел 1
- Узел 1 теперь должен указывать на узел 3
Для обоих нижеприведенных решений мы инициализируем «фиктивный» список, который является копией исходного LinkedList с фиктивным узлом, добавленным в его заголовок. Это позволяет нам легко манипулировать тем, что изначально было первым ListNode, а затем мы можем отрезать этот фиктивный узел в конце, вернув фиктивное свойство LinkedList .next.
Решение # 1: цикл while
В этом решении мы инициализируем копию исходного LinkedList, который мы будем использовать для его обхода, меняя местами по ходу. Затем мы запускаем цикл while до тех пор, пока в новом LinkedList остается 2 или более элементов, так как 2 требуются для выполнения обмена.
Наконец, мы меняем местами 2 узла, перемещаем 2 узла дальше в LinkedList, и процесс повторяется.
Решение # 2: рекурсивное
Этот подход более или менее идентичен циклу while, но немного более краток. Различия в производительности между двумя подходами в JavaScript незначительны.
