15、两两交换链表的节点

厨子2025/11/10大约 3 分钟数据结构算法算法基地面试链表三指针刷题程序厨校招社招

两两交换不是把节点里的数字互换，而是改变链表连接。只要把“一组内部怎样交换”与“前后组怎样接上”分开，指针操作就不必靠背模板。

问题与目标

LeetCode 24：两两交换链表中的节点要求将相邻节点两两交换，不修改节点的值。

1 → 2 → 3 → 4   变为   2 → 1 → 4 → 3
1 → 2 → 3       变为   2 → 1 → 3

最后剩一个节点时原样保留，空链表也直接返回空。

把一组操作拆成四个角色

prev 是前一组交换后的尾节点，first 和 second 是当前两个节点，after 是这一组后面的链表起点。

最前面放一个虚拟头节点 dummy，让第一组也拥有 prev，不必专门处理“交换后头节点变化”。虚拟头节点不进入答案，也不改变任何真实节点的值。

先保存后继，再修改连接

每组原本是 prev → first → second → after。我们按以下顺序修改：

保存 after = second->next，避免改线之后找不到剩余链表。
first->next = after，将交换后的尾节点接回后续。
second->next = first，完成组内反转。
prev->next = second，把前一组连到新的组头。

随后令 prev = first。注意，交换后是原来的 first 成为组尾，不是继续让 prev 指向 second。

C++17 实现

struct ListNode {
  int val;
  ListNode* next;
  explicit ListNode(int value, ListNode* following = nullptr)
      : val(value), next(following) {}
};

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;
      ListNode* after = second->next;
      first->next = after;
      second->next = first;
      prev->next = second;
      prev = first;
    }
    return dummy.next;
  }
};

复杂度与边界

每组只做固定次数指针操作，总时间 O(n)，额外空间 O(1)。没有创建新的真实链表节点，也没有释放原节点；节点的所有权仍属于调用者。

循环条件必须确认当前组有两个节点。先检查 prev->next，再检查它的后继，利用短路求值避免空指针访问。返回的是 dummy.next，不是局部虚拟头节点自己的地址。

常见误区

直接先写 first->next = second 并不能完成交换，因为原来就是这个方向；反复改指针却不保存后继容易断链；只交换 val 则不符合题意。调试时除了检查数值顺序，还应检查节点身份没有丢失、链表没有形成环。

延伸阅读