两两交换链表中的节点

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

题目描述

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能改变节点指针,不能只交换值)。

输入：head = [1,2,3,4]
输出：[2,1,4,3]
解释：(1,2) 交换成 (2,1)，(3,4) 交换成 (4,3)

输入：head = [1,2,3]
输出：[2,1,3]        // 最后落单的 3 保持不动

题目特意强调"不能交换值,只能改指针"。这就把问题从"平凡的赋值"提升为"链表指针操作训练"——每交换一对,都要小心地把三根指针(前驱、第一个、第二个)重新接好,还不能弄丢后面的链。

思路拆解

暴力解法:交换节点的值(不符合要求,但可对照)

最偷懒的想法:遍历链表,每两个相邻节点直接交换它们的 val。

点击展开「交换值」解法（本题明确禁止，仅作对照）

// 只换值不换指针 —— 本题要求「不能这么做」
function swapPairs(head) {
  let node = head;
  while (node && node.next) {
    const tmp = node.val;      // 交换相邻两节点的值
    node.val = node.next.val;
    node.next.val = tmp;
    node = node.next.next;     // 跳到下一对
  }
  return head;
}

为什么这种做法不可取？

题目明确规定只能改变指针,不能修改节点内部的值。现实中链表节点可能携带大量数据或不可变,交换值往往代价高甚至非法。面试中考察的正是指针操作能力,所以我们必须真正地"断开再重连"。

最优解法:迭代 + 哑节点 + 三指针

对每一对相邻节点 a、b,我们要把顺序 prev → a → b → 后续 改成 prev → b → a → 后续。引入哑节点 dummy 让"交换第一对"也有统一的前驱。

核心思路:三步接线(顺序不能乱)

设 prev 是当前这对的前驱,a = prev.next(第一个),b = a.next(第二个)。三步完成一次交换:

1. a.next = b.next —— a 越过 b,指向 b 后面的节点(先做,否则会丢失后续);
2. b.next = a —— b 回指 a,完成这对内部的反转;
3. prev.next = b —— 前驱指向 b,把交换好的这对接回链表。

交换后,a 成了这对的尾巴,把 prev 移到 a(prev = a),继续处理下一对。用箭头表示一次交换的变化:

循环条件是 prev.next && prev.next.next —— 保证这对里两个节点都存在,否则(剩 0 或 1 个)停止,落单节点自然保持不动。

递归写法(思路更简洁)

点击展开递归解法（优雅，但空间 O(n)）

// 交换前两个，剩下的交给递归
function swapPairs(head) {
  if (head === null || head.next === null) return head;

  const first = head;
  const second = head.next;

  first.next = swapPairs(second.next); // first 接上「后面递归交换好的结果」
  second.next = first;                 // second 回指 first

  return second; // second 成为这一段的新头
}

交互式动画演示

下面用样例 head = [1,2,3,4] 演示迭代三指针的完整过程。点击 下一步 逐步观察 prev、a、b 的定位与"三步接线"如何把每对节点交换:

步骤 1 / 12初始化

prev (前驱)a (第一个)b (第二个)

prev

D

→

1

→

2

→

3

→

4

→

null

初始化：哑节点 dummy 指向头节点 1，prev 停在 dummy。每次处理一对相邻节点。

完整代码(JavaScript)

高亮行为三步接线的核心,顺序至关重要。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function swapPairs(head) {
  const dummy = new ListNode(0, head); // 哑节点，统一第一对的前驱
  let prev = dummy;

  // 每对需要两个节点：prev.next 和 prev.next.next
  while (prev.next && prev.next.next) {
    const a = prev.next;      // 这对的第一个
    const b = a.next;         // 这对的第二个

    a.next = b.next;          // 步骤1：a 越过 b，接到 b 的后面
    b.next = a;               // 步骤2：b 回指 a
    prev.next = b;            // 步骤3：前驱指向 b，接回链表

    prev = a;                 // a 成了这对的尾，移动 prev 到 a
  }

  return dummy.next; // 用哑节点返回新头（第一对交换后 head 已变）
}

复杂度分析

设链表长度为 。

解法	时间复杂度	空间复杂度	说明
交换值(禁用)			不改指针,但违反题目要求
迭代三指针			一趟遍历,每对常数次指针操作
递归			递归栈深度为 ,即

边界与易错点

常见踩坑

1. 三步接线的顺序不能乱:必须先 a.next = b.next(保存后续),再 b.next = a,最后 prev.next = b。若先改 b.next = a,就会丢失 b 原来的后继,后面的链断掉。
2. 不用哑节点会丢头:交换第一对后,新头变成了原来的第二个节点。没有哑节点就得为"更新 head"单独写特判,哑节点让 dummy.next 永远指向正确的新头。
3. 循环条件写错:必须是 prev.next && prev.next.next(这对的两个节点都在)。写成只判一个会在奇数长度末尾越界或漏交换。
4. 忘记移动 prev:交换后 a 是这对的尾,应 prev = a 再进入下一对。忘记移动会造成死循环或重复交换。
5. 奇数长度 / 空链表:剩单个节点或空链表时,循环条件自然为假,落单节点保持原样,无需特判。
6. 返回值:要返回 dummy.next,不是 head(head 仍指向原第一个节点,交换后它已不是头)。

简易解题思路(记忆口诀)

一句话记忆:「哑节点开路,三步接线走,前驱跳到尾」

把每一对相邻节点想象成两个要换座位的同学 a 和 b,前排是 prev:

• 哑节点开路:在队首放一个"假班长"(dummy),这样连第一对换座也有人盯着;
• 三步接线走(顺序背死):
  1. a 伸手勾住 b 后面的人(a.next = b.next)——先拉住后队,别让它跑了;
  2. b 回头拉住 a(b.next = a)——两人完成对调;
  3. 前驱改牵 b(prev.next = b)——把换好的一对接回队伍;
• 前驱跳到尾:换完后 a 排在这对的最后,让 prev 走到 a,准备指挥下一对。

三步口诀:①a 勾后队 → ②b 拉 a → ③前驱牵 b → prev 跳到 a。 记住核心画面:"先拉后队防断链,再对调,最后接回去。"