Учитывая связанный список, поменяйте местами каждые два соседних узла и верните его заголовок.

Пример:

Учитывая 1->2->3->4, вы должны вернуть список как 2->1->4->3.

Примечание.

Ваш алгоритм должен использовать только постоянное дополнительное пространство.

Вы можете не изменять значения в узлах списка, можно изменять только сами узлы.

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

  • Итеративное решение - поменяйте каждую пару с головы до ног
ListNode* swapPairs(ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    
    ListNode dummy(0), *it = &dummy;
    it->next = head;
    while (it->next && it->next->next) {
        ListNode* post = it->next->next->next;
        ListNode* last = it->next;
        
        it->next->next->next = it->next;
        it->next = it->next->next;
        last->next = post;
        
        it = last;
    }
    
    return dummy.next;
}

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

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

Здесь обратите внимание, что после свопов заголовок нашего списка может измениться, если размер входного списка больше единицы, поэтому мы используем фиктивную голову в качестве заполнителя для объединения нашего списка результатов. Таким образом, мы можем начать с фиктивной головы с итератором списка (указателем) и проверить, существуют ли два последующих узла списка после текущего указателя, где it представляет собой хвост прежней части списка, который уже поменялся местами. Если их два, наша задача - поменять их местами, а затем перейти к следующей паре.

Для этого обратите внимание, что когда мы меняем местами текущую пару, вторая должна указывать на свой предыдущий узел, поэтому мы можем потерять след последующего списка. Вот почему мы используем указатель post для хранения заголовка следующего подсписка. Следующим шагом, видимо, будет своп. Мы разделим эту операцию на два этапа. Во-первых, мы буквально меняем местами эти два узла, указывая второй узел в паре на первый. Затем мы должны вставить новую замененную пару в правильное положение. Для этого нам нужно объединить новый передний узел в паре с хвостом предыдущего замененного списка и соединить последующий список с новым вторым узлом в паре. Наконец, обратите внимание, что переменная it представляет собой хвост замененной части списка, поэтому мы должны переместить ее в новый хвост. Так что же на самом деле представляет собой новый хвостовой узел? Ответ, по-видимому, старый первый узел в паре, так как после операции свопинга он идет до конца. Таким образом, мы могли бы просто позволить it указывать на этот старый первый узел (новый второй узел) и продолжать цикл.

Давайте попробуем небольшой пример:

Suppose that we have an input list:
1->2->3->4->5->NULL
Current List:       1->2->3->4->5->NULL
Initialization:     dummy -> 1, it = dummy
1st Iteration:      There are two nodes after it
                    let post store 3
                    point 2 to 1
                    point it to 2
                    point 1 to 3
                    move it to 1
Current List:       dummy->2->1->3->4->5->NULL
Data Structure:     it = 1
2nd Iteration:      There are two nodes after it
                    let next store 5
                    point 4 to 3
                    point it to 4
                    point 3 to 5
                    move it to 3
Current List:       dummy->2->1->4->3->5->NULL
Data Structure:     it = 3
3rd Iteration:      There is only one node after it
                    stop
Current List:       dummy->2->1->4->3->5->NULL
Data Structure:     it = 3
return dummy -> next = 2

Сложность времени: O (n) - нам нужно пройти весь список один раз. Таким образом, временные затраты линейны.

Сложность пространства: O (1) - единственная вспомогательная память, которую мы использовали, - это поддержка нескольких локальных указателей, которые должны иметь постоянную сложность пространства.

  • Рекурсивное решение

Теперь давайте посмотрим на реализацию рекурсии.

ListNode* swapPairs(ListNode* head) {
    if (!head || !head->next)
        return head;
    
    ListNode* post = swapPairs(head->next->next);
    ListNode* res = head->next;
    res->next = head;
    head->next = post;
    
    return res;
}

Для этой проблемы мы также можем попытаться разделить большую проблему на мелкие. Обратите внимание, что, учитывая заголовок списка, какие основные операции мы собираемся выполнить за одну итерацию? На каждой итерации мы пытались поменять местами текущую пару узлов, а затем перейти к следующим. Следовательно, в рекурсивном решении нам также удавалось менять местами только одну пару за раз и подключаться к полученному результату для всего последующего списка через рекурсивные вызовы.

Теперь давайте проанализируем рекурсивные правила:

  1. Базовый случай: входящий связанный список пуст или содержит только один единственный узел, который является его головой.
  2. Рекурсивное правило: 1) Поменяйте местами все пары в следующем подсписке. 2) Поменяйте местами текущую пару и правильно соедините их с результатом, полученным из последующего списка.

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

Затем, с точки зрения рекурсивных вызовов, нам нужно пропустить два текущих узла, поскольку мы поменяем их местами в текущем вызове функции. Таким образом, мы передадим третий узел в качестве головы следующему рекурсивному вызову и получим от него замененный результат. После получения результата от подзадачи мы просто поменяем местами текущую пару и вставим ее в начало результата подзадачи.

Давайте рассмотрим тот же пример, что и выше:

Suppose that we have an input list:
1->2->3->4->5->NULL
Current List:       1->2->3->4->5->NULL
In Main Function:   call swapList(1)
Current List:       1->2->3->4->5->NULL
In swapList(1):     call swapList(3)
Current List:       1->2->3->4->5->NULL
In swapList(3):     call swapList(5)
Current List:       1->2->3->4->5->NULL
In swapList(5):     hit base case
                    return 5
Current List:       1->2->3->4->5->NULL
In swapList(2):     get 5 from swapList(5)
                    let 4 point to 3
                    let 3 point to 5
                    return 4
Current List:       1->2->4->3->5->NULL
In swapList(1):     get 4 from swapList(2)
                    let 2 point to 1
                    let 1 point to 4
                    return 2
Current List:       2->1->4->3->5->NULL
In Main Function:   get 2

Сложность времени: O (n) - мы должны вызывать линейное время рекурсивных вызовов для всего списка, и в каждом вызове функции у нас есть постоянные временные затраты на операцию подкачки, поэтому вся временная сложность равно O (n).

Сложность пространства: O (n) - поскольку нам нужно сделать линейное время рекурсивных вызовов, использование стека вызовов составляет O (n). В каждом вызове функции нам нужно поддерживать только конечное количество указателей, поэтому в каждой функции стоимость пространства постоянна. Таким образом, вся сложность пространства равна O (n).

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