两两交换链表中的节点

方法一：迭代

前置知识

Python 解法1C++ 解法1

python

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node0 = dummy = ListNode(next=head)  # 用哨兵节点简化代码逻辑
        node1 = head
        while node1 and node1.next:  # 至少有两个节点
            node2 = node1.next
            node3 = node2.next

            node0.next = node2  # 0 -> 2
            node2.next = node1  # 2 -> 1
            node1.next = node3  # 1 -> 3

            node0 = node1  # 下一轮交换，0 是 1
            node1 = node3  # 下一轮交换，1 是 3
        return dummy.next  # 返回新链表的头节点

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0, head); // 用哨兵节点简化代码逻辑
        ListNode* node0 = &dummy;
        ListNode* node1 = head;
        while (node1 && node1->next) { // 至少有两个节点
            ListNode* node2 = node1->next;
            ListNode* node3 = node2->next;

            node0->next = node2; // 0 -> 2
            node2->next = node1; // 2 -> 1
            node1->next = node3; // 1 -> 3

            node0 = node1; // 下一轮交换，0 是 1
            node1 = node3; // 下一轮交换，1 是 3
        }
        return dummy.next; // 返回新链表的头节点
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为链表长度。
空间复杂度： $O (1)$ 。仅用到若干额外变量。

方法二：递归

前置知识

一看递归就晕？带你理解递归的本质！【基础算法精讲 09】

思路

和方法一类似。这里直接用 swapPairs 当作递归函数：

递归边界：如果 $head$ 或者 $head . next$ 为空，说明剩余节点不足两个，无需交换，返回 $head$ 。
先交换以 ${node}_{3}$ 为头节点的链表，即递归调用 swapPairs(node3)。
把 ${node}_{1}$ 指向递归返回的链表头。
把 ${node}_{2}$ 指向 ${node}_{1}$ 。
返回 ${node}_{2}$ ，作为交换后的链表头节点。

Python 解法3C++ 解法3

python

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:  # 递归边界
            return head  # 不足两个节点，无需交换

        node1 = head
        node2 = head.next
        node3 = node2.next

        node1.next = self.swapPairs(node3)  # 1 指向递归返回的链表头
        node2.next = node1  # 2 指向 1

        return node2  # 返回交换后的链表头节点

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* node1 = head;
        ListNode* node2 = head->next;
        ListNode* node3 = node2->next;

        node1->next = swapPairs(node3); // 1 指向递归返回的链表头
        node2->next = node1; // 2 指向 1

        return node2; // 返回交换后的链表头节点
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为链表长度。
空间复杂度： $O (n)$ 。递归需要 $O (n)$ 的栈空间。

思考题

如果改成每 $k$ 个节点一组反转链表呢？

这题是 25. K 个一组翻转链表，请看视频讲解。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：迭代 ​

前置知识 ​

复杂度分析 ​

方法二：递归 ​

前置知识 ​

思路 ​

复杂度分析 ​

思考题 ​

分类题单 ​

方法一：迭代

前置知识

复杂度分析

方法二：递归

前置知识

思路

复杂度分析

思考题

分类题单