算法

两两交换链表中的节点

loser

22 Aug 2026 • 6 min read

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

你必须在不修改节点内部的值的情况下完成本题，也就是只能进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [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) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy;

        while (prev->next != nullptr && prev->next->next != nullptr)
        {
            ListNode* first = prev->next;
            ListNode* second = first->next;

            first->next = second->next;
            second->next = first;
            prev->next = second;

            prev = first;
        }

        return 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 == nullptr || head->next == nullptr)
        {
            return head;
        }

        ListNode* first = head;
        ListNode* second = head->next;

        first->next = swapPairs(second->next);
        second->next = first;

        return second;
    }
};

核心思想

这题要求把链表中相邻的两个节点一组交换。

例如：

1 -> 2 -> 3 -> 4

交换后变成：

2 -> 1 -> 4 -> 3

题目要求只能交换节点，不能修改节点值。

所以我们要做的是重新调整指针，而不是交换 val。

这题最关键的观察是：

每次只处理链表中的前两个节点，把它们交换后，再递归或迭代处理后面的剩余链表。

解法一：迭代交换

为了统一处理头节点和后续节点，先使用虚拟头节点：

ListNode dummy(0, head);

prev 指向当前待交换这对节点的前一个节点。

在每一轮中，假设：

first = prev->next
second = first->next

也就是当前需要交换的两个节点。

交换过程分三步：

1. 让 `first` 跳过 `second`

first->next = second->next;

这样 first 先接上后面的链表，避免后续指针丢失。

2. 让 `second` 指向 `first`

second->next = first;

这样两个节点的相对顺序就反过来了。

3. 让前一个节点指向新的头节点 `second`

prev->next = second;

这样整对节点就被接回原链表中。

交换完成后，first 变成了这一对交换后的尾节点。

下一轮就从 first 继续处理后面的节点：

prev = first;

为什么每次要保存 `first` 和 `second`

交换节点时会修改指针。

如果不先保存：

ListNode* first = prev->next;
ListNode* second = first->next;

那么一旦改动了 next 指针，后面的链表就可能找不到了。

所以先记录这两个节点，再进行重连。

解法二：递归交换

递归思路也很直接：

先交换前两个节点，再递归处理剩余链表。

假设当前链表是：

first -> second -> rest

交换后应变成：

second -> first -> swap(rest)

所以：

first->next = swapPairs(second->next);
second->next = first;

递归终止条件是：

head == nullptr || head->next == nullptr

因为：

空链表不用交换
只有一个节点时，也没有成对节点可交换

边界情况

如果链表为空：

head = []

直接返回 nullptr。

如果链表只有一个节点：

head = [1]

没有第二个节点可以交换，结果仍然是它自己。

如果链表长度为偶数，例如：

head = [1,2,3,4]

每一对节点都可以完整交换，结果是：

[2,1,4,3]

如果链表长度为奇数，例如：

head = [1,2,3]

前两个节点交换后，最后的 3 没有配对节点，保持原样：

[2,1,3]

正确性证明

我们证明：算法返回的链表是每两个相邻节点交换后的结果。

结论 1：迭代过程中，每一轮都会正确交换当前这对节点

设当前待交换的两个节点为 first 和 second。

交换前，它们与前后节点的连接关系是：

prev -> first -> second -> rest

先执行：

first->next = second->next;

得到：

first -> rest

再执行：

second->next = first;

得到：

second -> first -> rest

最后执行：

prev->next = second;

就把交换后的这一对重新接回原链表。

因此每一轮都能正确交换当前这对节点。

结论 2：迭代过程不会丢失后续链表

在交换前，已经先保存了：

second->next

并且 first->next 会先指向它。

所以后面的链表不会被断开或丢失。

每一轮交换后，prev 都移动到交换后的尾节点 first，继续处理后面的部分。

因此整个链表都会被依次处理完。

结论 3：递归解法中，前两个节点交换后，剩余部分会被正确处理

当链表长度小于 2 时，直接返回，结果显然正确。

当链表长度至少为 2 时，当前前两个节点交换后，剩余部分是：

second->next

递归调用：

swapPairs(second->next)

可以保证剩余部分也被正确交换。

然后再把：

first->next = ...
second->next = first;

连起来，就得到了整条链表的正确结果。

得出结论

由结论 1 和结论 2 可知，迭代解法能正确交换所有成对节点，并保持链表完整。

由结论 3 可知，递归解法也能正确完成相邻节点交换。

因此两个解法都正确。

举例理解

以：

head = [1,2,3,4]

为例。

第一轮交换前两个节点：

1 -> 2 -> 3 -> 4

交换后变成：

2 -> 1 -> 3 -> 4

然后继续处理后面的 3 -> 4。

第二轮交换：

2 -> 1 -> 4 -> 3

最终结果是：

[2,1,4,3]

如果是：

head = [1,2,3]

第一轮交换后：

2 -> 1 -> 3

最后的 3 没有配对节点，因此保持不变。

复杂度分析

解法一

每个节点只会被访问和重连一次。

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

解法二

每次递归处理两个节点。

递归深度约为 n / 2。

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

如果追求空间最优，迭代解法更推荐。