交换链表中的节点：从指针重连到场景实战的完整拆解

引子

前两天一个朋友发消息问我：“Leetcode 108 交换链表中的节点怎么写？”我愣了一下，因为 LeetCode 上编号 108 其实是“将有序数组转换为二叉搜索树”，跟链表交换压根不是同一道题。但他又补了一句：“就是那种把正数第 k 个和倒数第 k 个节点互换的题，我老记不住编号。”我一下子明白了——他想问的其实是链表操作里最经典、最考基本功的一类问题：交换链表中的节点。

这类题目确实容易让人记混编号，但题目本身的含金量不容小觑。链表的节点交换，表面上只是“改两个指针”的事，实际上牵扯到边界判断、指针重连顺序、头节点更新、相邻节点特判等一系列问题。不管是刷题准备面试，还是日常写代码处理缓存队列、任务链表，掌握节点交换的底层逻辑，都能帮你少踩很多坑。

这篇文章就用“交换链表中的节点”这个主题，从最本质的“交换值还是交换指针”说起，再拆解两类最典型的交换场景——正数第 k 个与倒数第 k 个交换、相邻节点两两交换——最后把节点重连的思想延伸到合并有序链表、循环链表、去重等场景，并整理一份高频问题排查清单。内容偏实操，代码以 Python 为主，关键场景附 C++ 对照，适合正在刷链表题的初学者，也适合想在真实工程里把链表用扎实的开发同学。

1. “交换节点”到底在交换什么

1.1 两种交换思路：改值还是改链

很多初学者第一次写“交换链表中的节点”时，第一反应就是：找到两个节点，把它们的 val 换一下不就完事了？

这个思路放在数组里完全成立。数组是连续内存，元素本身就在那儿，交换两个下标对应的值，数组结构完全不变。但链表不一样。链表是由一个个独立分配出来的节点构成的，节点之间靠 next 指针串联。值只是节点携带的数据，指针才是决定“谁在前、谁在后”的关键。如果你只换值不换指针，那么节点的实际位置没有变，只是“人换了，座位没换”。这在某些场景下结果一样，但不是所有场景都行。

举个例子：如果链表节点不只是存一个 int，而是存了一个带 key 的对象、一条日志记录、或者一个带引用关系的复杂结构，那“值交换”就要拷贝整块数据，甚至可能因为对象内部有指针而出现浅拷贝问题。换指针只需要修改几个 next 指向，开销恒定，而且不破坏节点内部的完整性。

从面试官的视角看，只换值往往会被判定为“没有真正理解链表”。因为如果只是换值，你根本不需要讨论头节点变化、相邻节点特判这些链表操作的核心难点。这些难点恰恰是面试官想考察的东西。

1.2 一个直观的类比：火车车厢与挂钩

把链表想象成一列火车。每节车厢是一个节点，车厢里装货物就是节点的 val，车厢之间的挂钩就是 next 指针。

现在要求你把第 3 节车厢和第 8 节车厢的位置换一下。你有两种做法：

• 第一，把第 3 节的货物搬到第 8 节，把第 8 节的货物搬到第 3 节。车厢原地不动，但货物换了——这就是“值交换”。
• 第二，把第 3 节和第 8 节车厢从整列火车中拆下来，重新调整前后挂钩，让它们互换位置——这就是“指针交换”。

第一种方法操作起来很快，但要是每节车厢还拉着冷藏柜、油罐、危险品标识这些“附加属性”，搬货物就非常麻烦。第二种方法虽然要动挂钩，但只要拆挂得当，整列车还是完整的，每节车厢的“身份”也保持不变。

在算法题里，两种方法都能通过测试用例，但“指针交换”才是正路。因为很多进阶题目——比如反转链表、K 个一组翻转——全都建立在“改变节点连接关系”这个基础上。如果你只会换值，遇到这些题还是会卡住。

1.3 什么时候可以换值，什么时候必须换指针

我个人的判断标准是：

所以，我在写“交换链表中的节点”这类题时，默认就按“改指针”来写。本文后面所有代码也都基于这一点。

2. 核心场景一：交换正数第 k 个和倒数第 k 个节点

2.1 题目理解与难点

这个场景对应的经典题是 LeetCode 1721，题名就是 Swapping Nodes in a Linked List，和“Leetcode 108 交换链表中的节点”这个口头说法完全对得上。

题目要求很简单：给定一个链表和一个整数 k，把正数第 k 个节点和倒数第 k 个节点的值交换。链表长度未知，且题目限制只能遍历一次。

难点有三个：

1. 不遍历两次，怎么知道倒数第 k 个节点在哪？
2. 如果交换的是头节点，怎么保证返回的头节点正确？
3. 如果正数第 k 个和倒数第 k 个是同一个节点，或者两个节点相邻，怎么处理？

这三个问题，正好对应了链表操作里最经典的三个考察点：快慢指针、虚拟头节点、边界特判。

2.2 快慢指针定位倒数第 k 个节点

先说怎么只遍历一次就找到倒数第 k 个节点。

思路是这样的：先让一个指针 first 从链头出发，走 k-1 步，停在正数第 k 个节点上。再让另一个指针 second 从链头出发，和 first 同步往后走。当 first 走到链表末尾（等于 NULL）时，因为 second 和 first 之间始终保持着 k 个节点的距离，所以 second 恰好停在倒数第 k 个节点上。

这个技巧的本质是：两指针间距固定，终点确定，起点就确定了。就像两个人跑步，一个跑得快，一个跑得慢，但前后始终差 k 米。当快的人冲过终点线时，慢的人距离终点正好 k 米。

手动模拟一下更清楚。假设链表是 1 -> 2 -> 3 -> 4 -> 5，k = 2：

倒数第 2 个节点就是 4，和正数第 2 个节点 2 交换，结果是 1 -> 4 -> 3 -> 2 -> 5。

这里面有一个细节：first 先走的是 k-1 步，不是 k 步。因为 first 本身已经在第 1 个节点上，要走到第 k 个节点，只需要走 k-1 次 next。这个细节很多人写错，多走一步或少走一步，整个指针位置就偏了。

2.3 完整实现：Python 与 C++

先看 Python 版本。我给每行都加了注释，方便新手逐行对照。

python复制class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def swap_nodes(head, k):
    # 1. 快指针 fast 先走 k-1 步，定位到正数第 k 个节点
    fast = head
    for _ in range(k - 1):
        fast = fast.next

    # 2. 把 fast 当前的位置记住，这就是正数第 k 个节点
    first = fast

    # 3. 慢指针 slow 从头部开始，和 fast 同步移动
    slow = head
    while fast.next:
        fast = fast.next
        slow = slow.next

    # 4. slow 此时就是倒数第 k 个节点
    second = slow

    # 5. 交换两个节点的值（这里交换值而不是交换指针）
    first.val, second.val = second.val, first.val

    return head

注意，这段代码我用的是“交换值”，不是“交换指针”。因为这道题只要求交换两个节点的 val，没要求保持节点身份。用值交换可以避开“交换头节点后如何返回”的麻烦，代码最简洁。

但如果你想练习“交换指针”，或者面试官追问“你试试交换节点本身”，可以看下面这版。这版的边界判断会复杂很多。

python复制def swap_nodes_by_link(head, k):
    dummy = ListNode(0, head)

    # 定位正数第 k 个节点的前驱
    prev_first = dummy
    for _ in range(k - 1):
        prev_first = prev_first.next

    # 定位倒数第 k 个节点的前驱
    prev_second = dummy
    fast = prev_first.next
    while fast.next:
        fast = fast.next
        prev_second = prev_second.next

    first = prev_first.next
    second = prev_second.next

    # 交换前驱的下一个指向
    prev_first.next, prev_second.next = second, first

    # 交换后继
    first.next, second.next = second.next, first.next

    return dummy.next

这版代码能跑，但有个隐藏问题：如果 first 和 second 相邻，或者 first 就是 second 的前驱，交换后继那一步会互相覆盖。解决方法是先判断两个节点是否相邻，相邻时走单独的交换逻辑。这段代码故意保留了这个问题，目的就是让你知道“指针交换”的边界处理有多烦。

C++ 版本如下，结构体定义放在注释里，方便对照结构体链表基本语法。

cpp复制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* swapNodes(ListNode* head, int k) {
        ListNode* fast = head;
        for (int i = 0; i < k - 1; ++i) {
            fast = fast->next;
        }
        ListNode* first = fast;

        ListNode* slow = head;
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* second = slow;

        swap(first->val, second->val);
        return head;
    }
};

C++ 的写法差别不大，核心逻辑完全一样。需要注意的只是语言层面：C++ 里要手动管理内存，但刷题场景通常不用 delete，只要能通过编译即可。

2.4 虚拟头节点：为什么交换头节点时它很有用

很多链表操作题里都要加一个 dummy 节点，也就是虚拟头节点。它的作用只有一个：让原本“需要特殊处理的头节点”变成“普通节点”。

怎么理解？假设你要交换的节点正好是头节点。如果没有 dummy，交换完成后你没法直接拿到新头节点——因为链表的入口 head 已经变了。你必须先判断“被交换的节点里有没有 head”，然后手动更新 head。

有了 dummy 之后，题目就变成了“在 dummy 后面的一条链表中交换两个节点”，不管交换的是不是原链表的头节点，我们都能通过 dummy->next 拿回完整的链表。这就是虚拟头节点最大的价值：把边界情况化归为普通情况。

我在写链表题时，只要涉及“可能改动头节点”的操作，无条件先建一个 dummy，可以省掉大量 if 判断。

2.5 这道题最容易错的三个地方

先想清楚这个问题：k 等于链表长度时，正数第 k 个节点就是倒数第 1 个节点，此时 first 和 second 指向同一个节点。交换同一个节点没有意义，程序也不会报错，但你要确保不会因为第一节点被交换而丢链。

其次是“快指针先走 k-1 步”这个细节。多走一步，first 可能直接指向 NULL，后面所有操作都会空指针崩溃。

最后是“链表长度小于 k”的输入。真实面试中面试官不会给这种用例，但刷题时如果没判断，会拿到一个空指针异常。保险起见可以在开头判断一次，虽然题目默认输入合法。

3. 核心场景二：相邻节点两两交换

3.1 题目背景与迭代思路

如果说“正数第 k 个和倒数第 k 个交换”考的是定位能力，那“相邻节点两两交换”（LeetCode 24）考的就是指针重连的顺序感。

题目要求：给定 1 -> 2 -> 3 -> 4，返回 2 -> 1 -> 4 -> 3。如果是奇数个节点，最后一个节点保持原样。

迭代法的套路是：维护一个 prev 指针，表示已经处理完的链表尾部；再维护 cur 和 nxt 表示当前要交换的两个相邻节点。每次循环，把 prev 的 next 接到 nxt 上，把 nxt 的 next 接到 cur 上，再把 cur 的 next 指向下一轮的第一个节点，最后更新 prev 和 cur。

这个过程用文字说容易绕，换成代码就清楚得多。下面这版代码使用 dummy，避免头节点被交换后返回错误。

python复制def swap_pairs(head):
    dummy = ListNode(0, head)
    prev = dummy

    while prev.next and prev.next.next:
        cur = prev.next
        nxt = cur.next

        # 核心三连：改变三个指针
        prev.next = nxt
        cur.next = nxt.next
        nxt.next = cur

        # 移动 prev 到下一对的前一个位置
        prev = cur

    return dummy.next

关键就是循环里那三行赋值。很多人写错是因为顺序不对：如果先把 cur.next 改了，再想找 nxt.next 就会拿到错误节点。所以在改指针之前，要把 cur、nxt、nxt.next 这三个节点先保存下来。这是一条铁律：改指针前，先保存后继。

手动模拟一下 1 -> 2 -> 3 -> 4：

初始：dummy -> 1 -> 2 -> 3 -> 4，prev = dummy，cur = 1，nxt = 2。

执行三连：

• prev.next = nxt → dummy -> 2
• cur.next = nxt.next → 1 -> 3
• nxt.next = cur → 2 -> 1

此时链表是 dummy -> 2 -> 1 -> 3 -> 4，prev = 1，下一轮 cur = 3，nxt = 4。再走一轮，得到 dummy -> 2 -> 1 -> 4 -> 3。

这个过程里最关键的认知是：节点本身没有被创建或删除，只是 next 指针重新指向了新的邻居。链表还是那四个节点，但顺序变了。

3.2 递归解法：链表天然适合递归

两两交换也可以用递归写，而且代码非常短。

python复制def swap_pairs(head):
    if not head or not head.next:
        return head

    first = head
    second = head.next

    first.next = swap_pairs(second.next)
    second.next = first

    return second

递归的思路是：先把当前这一对的 next 关系处理掉，剩下的子链表交给递归函数继续处理。对 1 -> 2 -> 3 -> 4 来说：

• 调用 swap_pairs(1)：first=1, second=2。
• first.next 被赋值为 swap_pairs(3) 的返回结果。
• swap_pairs(3)：first=3, second=4，3.next 被赋值为 swap_pairs(NULL)，也就是 NULL；4.next=3；返回 4（即新的子链头，4 -> 3）。
• 所以在原来的调用里，1.next = 4，2.next = 1，最后返回 2。
• 最终链表：2 -> 1 -> 4 -> 3。

递归解法虽然简洁，但要注意：链表很长时会占用 O(n) 的调用栈空间。刷题时没问题，真实工程里如果链表有成千上万个节点，可能会栈溢出。我自己的习惯是：笔试面试用递归展示思路，实际项目里用迭代。

3.3 相邻节点交换的细节陷阱

相邻节点交换最大的坑在于“指针重连后，原来的 cur 去哪了”。看第 3.1 节的代码，循环结束时 prev = cur。这时候 cur 已经被换到 nxt 后面去了，但 prev 原本是“这一对的第一个节点”，现在正好是“下一对的前一个节点”，所以 prev = cur 是正确移动。

另一个容易错的地方是循环条件。while prev.next and prev.next.next 的意思是“当前节点和它的下一个节点都存在时，才执行交换”。如果链表只有 0 个或 1 个节点，循环体不执行，直接返回原链表。这个条件写成 while cur and cur.next 也能跑，但这样就少了一个 prev 的语义，代码逻辑会变乱。

还有一个实战技巧：调试链表题时，写一个打印函数，每执行一轮交换就打印一次链表，非常直观。我用这个办法找回过无数次“指针断链”的问题。

python复制def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

4. 延伸场景：合并有序链表与循环链表

4.1 合并两个有序链表：节点交换思想的直接应用

热词里反复出现“合并两个有序的单链表”“单链表的基本操作实验”，这说明链表的节点重连思想被用在了很多相邻场景上。交换节点是在“两个节点之间”改指针，合并两个链表则是在“两个链表之间”反复选择更小的节点并接到结果链表尾部。本质上都是同一件事：不改变节点的值，只改变节点的 next 指向，重新组织节点顺序。

LeetCode 21 就是这道题。迭代解法如下：

python复制def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    tail = dummy

    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next

    tail.next = list1 if list1 else list2
    return dummy.next

这里的核心操作是：tail.next 指向两个头节点中较小的那个，然后把 list1 或 list2 的头节点向后移动一位，tail 也向后移动一位。每一次循环都在做“选择、连接、推进”三步，和交换节点时“保存后继、改指针、更新指针”的套路一模一样。

递归版本也很经典：

python复制def merge_two_lists(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1

    if list1.val <= list2.val:
        list1.next = merge_two_lists(list1.next, list2)
        return list1
    else:
        list2.next = merge_two_lists(list1, list2.next)
        return list2

这个递归解法的思维方式是：当前最小的节点一定在 list1 或 list2 的头节点里，选出来之后，剩下的两个链表继续做同样的合并。递归好处是代码短、逻辑清晰，坏处同样是栈深度。

4.2 循环链表的特殊性：边界不再是 NULL

热词里的“循环单链表”“单循环链表”是另一个经典话题。循环链表和普通链表的唯一区别是：尾节点的 next 指向头节点，而不是 NULL。这个区别导致很多操作发生了变化。

比如在循环链表中，判断“到达结尾”不能用 while node is not None，而要用 while node.next != head。遍历时也要额外小心，否则容易死循环。

再比如，“交换头尾节点”在普通链表里是个边界操作，在循环链表里反而更像普通操作，因为尾节点后面就是头节点，两个节点天然相邻。但如果你用快慢指针定位中间节点时，循环链表里“快指针走到尾”的判断条件会特别容易写错，需要用不同的速度指针相遇来判断环。

还有一道经典的循环链表题目是“判断链表是否有环”。解法就是快慢指针：快指针每次走两步，慢指针每次走一步，如果链表有环，两者一定会在环内相遇。这个题目本身不涉及节点交换，但它和“交换节点”共享同一套底层工具——双指针。这也是为什么我建议把节点交换、环形链表、合并有序链表放一起刷，练的是同一个思维模型。

4.3 链表去重与集合差集：重连思想的其他应用

热词里还有“边缘节点去重算法”“基于链表的两个集合的差集”。这些说法在数据结构教材里通常会出现在“有序链表的去重”和“两个有序链表求差集”的实验中。

有序链表去重的核心思路很简单：当前节点和下一个节点值相同时，把当前节点的 next 指向下下个节点，跳过重复节点；值不同时，当前节点向后移动。这本质上也是“改指针、保存后继”的套路。

python复制def delete_duplicates(head):
    cur = head
    while cur and cur.next:
        if cur.val == cur.next.val:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return head

两个有序链表求差集，思路是：同时遍历两个链表，如果 A 的值小于 B 的值，说明 A 的节点不在 B 中，加入结果链表；如果 A 的值大于 B 的值，B 向后走；如果相等，两个链表都向后走。每一步还是在“选择、连接、推进”。所以你会发现，链表题做多了之后，很多题目都是换汤不换药，底层就那几个动作。

5. 真实工程里的“节点”：从链表到复杂系统

5.1 ComfyUI 节点、ROS 节点与链表节点：只是类比

热词里出现了“comfyui 节点管理器中文”“QwenImageEditPlus 节点”“ros 多个节点发布移动指令话题时底盘节点如何取舍”这些内容。这些“节点”和数据结构的链表节点完全是两码事，但它们的共性在于：都是“一个独立的处理单元，通过某种连接关系与其他单元协作”。

拿 ComfyUI 这种图像生成工作流来说，每个节点负责一个独立任务，比如加载模型、正向推理、图像解码，节点之间用连线串联，前一个节点的输出是后一个节点的输入。如果把这个结构抽象成一个链表，每个节点就是 ListNode，输出到输入的连线就是 next 指针。理解了链表的“保存后继、切断、重连”思路，你就能理解为什么在 ComfyUI 里插入一个节点，本质上是改两条连线，而不是复制节点内容。

ROS 的节点系统也类似。多个节点同时发布移动指令，底盘节点如何取舍，本质上是一个“多输入合并”的编排问题。合并的规则可能是优先级、时间戳、权重，但不管你选哪种，最后底盘节点要做的都是“只保留一路输入，把其他输入断开”。这和链表合并时“每次选一个更小的节点接到结果尾部”在思维上是同构的。

不过我要明确说：这些系统内部的实现远比链表复杂，图结构、消息队列、依赖检查、条件分支都不是链表能覆盖的。这里讲类比只是为了帮你建立“节点重连”的心智模型，真要动手做这类系统，还是得老老实实看文档。

5.2 链表的指针思维能迁移到什么场景

以我个人的经验，链表训练出来的“指针思维”至少能迁移到三个场景：

第一，理解内存管理。链表节点的动态分配和指针重连，天然就是 C/C++ 内存管理的一个缩影。你写熟了链表，再去看智能指针、引用计数，会非常顺畅。

第二，理解缓存淘汰算法。LRU 缓存最经典的实现方式就是“哈希表 + 双向链表”。每次访问一个节点，要把节点摘下来放到头部，这就是“删除节点 + 头插节点”的组合，和“交换节点”用的是同一套指针操作。

第三，理解文件系统和树形结构。“叶子节点”“根节点”这些热词来自树结构，但树的遍历和链表遍历并没有本质区别，只是多了左孩子和右孩子两个指针。链表练会了，再去写二叉树遍历、二叉搜索树插入删除，手感会好很多。

这也是为什么我建议所有程序员都认真刷链表题：看似简单的数据结构，却是通向复杂数据结构的第一个台阶。

5.3 别把所有“节点”都当成链表

有一点要提醒：图结构里的节点和链表节点差距很大。链表是线性结构，每个节点最多一个后继；图是网状结构，一个节点可能连接到任意多个节点。如果你把图的遍历写成链表的 while 循环，会陷入死循环或漏遍历。

所以在真实工程里，看到“节点”这个词，先搞清楚底层结构是线性表、树还是图，再决定用哪套算法。这也是区分“只会刷题”和“真会写工程代码”的一个重要标志。

6. 常见问题与排查经验清单

6.1 高频 Bug 速查表

我整理了链表节点操作里最常见的 6 个问题，附带现象、原因和解法，供你刷题和写代码时对照排查。

6.2 我的独家排错技巧

第一个技巧是“画图调试”。不要觉得画图浪费时间。遇到链表题，先在纸上画一个 1 -> 2 -> 3 -> 4 -> 5 的链表，然后用箭头标出每个指针变量的指向。写出循环体的每一步后，对照图检查一遍，你会发现 90% 的错误在落代码之前就能发现。

第二个技巧是“三用例自检法”。写完链表题，不要急着提交，先用三个最小用例自测：空链表、只有一个节点的链表、两个节点的链表。这三个用例能覆盖绝大多数边界问题。

第三个技巧是“断言辅助调试”。在代码里加一个函数，检查链表完整性，比如验证每个节点的 next 都不指向自身，验证链表中节点总数不变（排除断链或误建节点）。刷题阶段这个辅助函数很有用，但提交前记得删掉。

python复制def assert_list(head, expected_len):
    count = 0
    while head:
        count += 1
        head = head.next
    assert count == expected_len, f"List length changed: {count}"

第四个技巧是“值交换兜底法”。如果你在真实项目里只是需要“把两个节点的数据交换”，而不是“交换节点的身份”，直接用值交换是最稳的。很多工程场景其实不需要节点身份互换，这时候强行做指针交换，只会引入不必要的复杂度。

6.3 从交换节点到更多经典题：后续可以刷的这些

掌握了节点交换的基础之后，可以按这个顺序继续刷：

• LeetCode 206 反转链表：核心是“逐个把节点摘下，头插到新链表”，用的还是保存后继、改指针那套动作。
• LeetCode 25 K 个一组翻转链表：相当于“分组反转”，每次反转 k 个节点，反转完还要把边界接上，非常考验指针操作的稳定性。
• LeetCode 19 删除链表倒数第 N 个节点：也用快慢指针定位，定位后做删除操作，和交换节点的定位过程一模一样。
• LeetCode 61 旋转链表：把链表从某个位置断开并移到头部，本质是“找断点 + 重连整条链”。

这四道题刷完，链表操作的基本功就相当扎实了。

最后说点个人体会

我最早写“交换链表中的节点”时，也偷懒用过换值。当时觉得题目能过就行，何必折腾指针。直到后来在项目里写一个 LRU 缓存，需要用双向链表维护访问顺序，才发现“换值”根本救不了场——因为缓存节点外面还挂着哈希表的引用，你一换值，哈希表指向的数据就变了。那时候才老老实实补了指针交换的课。

所以如果你想真正掌握链表，我建议别绕开指针操作。刷题的时候，哪怕题目只需要交换值，也试着用交换指针的方式写一遍，再对比两者差异。这个练习非常值。

最后再分享一个小技巧：做链表题时，把“保存后继”四个字写在草稿纸最显眼的位置。所有指针断链事故，几乎都源于这四个字没做到。链表不难，难的是细心，而细心是可以靠流程保证的。