24. Swap Nodes in Pairs 成对交换节点

题目链接
tag:

• Medium；
• DFS；

question：
  Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example2:

Input: head = []
Output: []

Example3:

Input: head = [1]
Output: [1]

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

方法一：递归
思路：这道题不难，基本的链表题，递归的写法比较简洁，实际上利用了回溯的思想，递归遍历到链表末尾，然后先交换末尾两个，然后依次往前交换，代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        // 递归，实际上利用了回溯的思想，递归遍历到链表末尾，然后先交换末尾两个，然后依次往前交换：
        ListNode* newHead = head->next;
        head->next = swapPairs(head->next->next);
        newHead->next = head;
        return newHead;
    }
};

方法二：迭代
思路：对于迭代实现，还是需要建立 dummy 节点，令cur表示当前到达的节点，初始时cur = dummy。每次需要交换 cur 后面的两个节点。
  如果 cur 的后面没有节点或者只有一个节点，则没有更多的节点需要交换，因此结束交换。否则，获得 cur 后面的两个节点 node1 和 node2，通过更新节点的指针关系实现两两交换节点。

具体而言，交换之前的节点关系是 temp -> node1 -> node2，交换之后的节点关系要变成 temp -> node2 -> node1，因此需要进行如下操作。

temp.next = node2
node1.next = node2.next
node2.next = node1

完成上述操作之后，节点关系即变成 temp -> node2 -> node1。再令 cur = node1，对链表中的其余节点进行两两交换，直到全部节点都被两两交换。

两两交换链表中的节点之后，新的链表的头节点是 dummy->next，返回新的链表的头节点即可。
参见代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        // 迭代，两两交换即可
        ListNode* dummy = new ListNode(-1), *cur = dummy;
        cur->next = head;
        while (cur->next && cur->next->next) {
            ListNode* node1 = cur->next;
            ListNode* node2 = cur->next->next;
            cur->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            cur = node1;
        }
        return dummy->next;
    }
};