24. 两两交换链表中的节点

力扣题目链接

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路

这道题目正常模拟就可以了。

建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。

对虚拟头结点的操作，还不熟悉的话，可以看这篇链表：听说用虚拟头节点会方便很多？。

接下来就是交换相邻两个元素了，此时一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序

初始时，cur指向虚拟头结点，然后进行如下三步：

操作之后，链表如下：

看这个可能就更直观一些了：

对应的C++代码实现如下：（注释中详细和如上图中的三步做对应）

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位，准备下一轮交换
        }
        return dummyHead->next;
    }
};

时间复杂度：$O(n)$
空间复杂度：$O(1)$

新思路

class Solution {
    public ListNode swapPairs(ListNode head) {
        /*
        递归法:
        宗旨就是紧紧抓住原来的函数究竟返回的是什么?作用是什么即可
        其余的细枝末节不要细究,编译器会帮我们自动完成
         */
        // base case
        if (head == null || head.next == null) return head;
        
        // swapPairs(ListNode head) 的意义就是两两翻转链表中的节点+返回翻转后的新的头结点
        // 我们知道翻转后新的头结点必然是第二个节点
        // 举例子:1->2->3->4 翻转后:2->1->4->3
        ListNode newHead = head.next; // 2
        // 此时tmpHead为:4->3
        ListNode tmpHead = swapPairs(newHead.next);
        // 而前面的还粘连着:1->2->(3)  4->3
        // 此时再让1->4 此时链表为:2->(3) 1->4->3
        head.next = tmpHead;
        // 再将2指向1即可 此时链表为:2->1->4->3 已经完成翻转
        newHead.next = head;
        // 返回新的头结点
        return newHead;
    }
}