复盘 · LC 24 两两交换链表中的节点

题目

• 题号：LeetCode 24
• 名称：两两交换链表中的节点（Swap Nodes in Pairs）
• 难度：Medium
• 链接：leetcode.cn/problems/swap-nodes-in-pairs
• 今日代码：24-两两交换链表中的节点/index.js

题意

给定单链表头结点，两两交换相邻节点（交换节点本身，不是只改 val），返回新头。

• 节点个数为奇数时，最后落单的那个不动。
• 空链、单节点都是合法输入。

边界：[]、[1]、[1,2]、[1,2,3]、偶长度长链。

涉及算法

标签	一句话
哨兵 + 迭代	dummy 统一「换头」；每轮用 prev / a / b 改三条边
递归	先交换当前对，再让剩余子链递归交换后接回来

教程对照：12 · 链表基础（哨兵）、13 · 链表进阶 练习清单含本题。

评价我的解法

我的代码（摘自 24-两两交换链表中的节点/index.js，不含本地测例）：

var swapPairs = function (head) {
  if (!head) {
    return null;
  }
  if (!head.next) {
    return head;
  }
  let cur = head,
    next = head.next;
  let nextNext = null,
    pre = null;
  while (cur && next) {
    if (next.next) {
      nextNext = next.next;
    } else {
      nextNext = null;
    }
    if (!pre) {
      head = next;
    } else {
      pre.next = next;
    }
    cur.next = next.next;
    next.next = cur;
    pre = cur;
    if (nextNext) {
      cur = nextNext;
    } else {
      cur = null;
    }
    if (nextNext && nextNext.next) {
      next = nextNext.next;
    } else {
      next = null;
    }
  }
  return head;
};

能 AC，交换顺序也对：先挂 cur.next，再让 next 指回 cur，再用 pre 接上一对。

• 时间 O(n)，空间 O(1)——量级没问题。
• 对在哪：迭代改指针、奇偶长度都能走到；本地还测了奇数长度。
• 糙在哪：
  1. 没有哨兵，第一轮用 if (!pre) head = next 特判换头，和后面「pre.next = next」两套逻辑。
  2. nextNext / cur / next 的推进全是 if/else 写满，可读性差，也更容易在改指针时看晕。
  3. nextNext = next.next 直接赋值即可，不必再分支。

面试口述会偏长；标准解用 dummy 后循环体只有固定几行。

最佳题解

哨兵 + 三指针（推荐默写）：

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  while (prev.next && prev.next.next) {
    const a = prev.next;
    const b = a.next;
    // prev -> a -> b -> ... 变成 prev -> b -> a -> ...
    prev.next = b;
    a.next = b.next;
    b.next = a;
    prev = a;
  }
  return dummy.next;
};

• 时间 O(n)，空间 O(1)。
• 为何更优：换头、中间、尾部落单都走同一套；prev 始终停在「下一对的前驱」，推进清晰。

递归版（短，但栈深 O(n)）：

var swapPairs = function (head) {
  if (!head || !head.next) return head;
  const next = head.next;
  head.next = swapPairs(next.next);
  next.next = head;
  return next;
};

面试优先讲迭代哨兵；递归可作加分口述。

关联题目

题	为何相关
206. 反转链表	改指针的基本功；24 是「局部反转长度为 2」
25. K 个一组翻转链表	24 的推广：每组长度 K
92. 反转链表 II	区间内改指向，同样依赖前驱哨兵感

一句话带走

两两交换：dummy + 每轮 prev/a/b 改三条边，奇节点自然停——别用「第一轮特判换头」拆两套逻辑。