LeetCode 24. 两两交换链表中的节点

2026-06-11 HGNULB 约 4 分钟

文章信息 21 个分类 3 个标签

分类

LeetCode CodeTop 中等已解决需加强 50-100 字节跳动微软美团阿里巴巴快手腾讯猿辅导滴滴京东华为拼多多网易旷视亚马逊 LeetCode 热题 100

题目描述

✅ 24. 两两交换链表中的节点

题意分析

给定链表头节点，把相邻的两个节点两两交换，返回交换后的头节点。题目明确要求交换节点本身，而不是修改节点内部的值——这是本题唯一的硬约束，也是它区别于「换值糊弄」的地方。

交换是按位置成组进行的：第 1、2 个节点一组，第 3、4 个节点一组，以此类推。链表长度为奇数时，末尾落单的那个节点不属于任何一组，原样保留，不参与交换。

边界信号：节点数范围是 [0, 100]，所以空链表和单节点链表都必须能直接返回；另外只要链表非空，原头节点一定会被交换到第二个位置——返回的头节点会变，这是一个提醒你处理好「头部特殊性」的信号。

解法：哨兵节点迭代交换相邻节点

核心思路

问题关键：交换的不是节点值，而是节点之间的连接。每组交换后，第二个节点成为组头、第一个节点成为组尾，还要把上一组、当前组和下一组重新接好。

为什么选哨兵迭代：第一组交换后头节点会改变，哨兵 dummy 为第一组补出统一的前驱，避免单独处理链表头；迭代只需常数空间，也比递归版更容易控制指针连接。

循环不变量：每轮开始时，pre 之前的节点已经按两两交换完成，pre 是已处理部分的尾节点，也是下一组的前驱。令 first = pre.next、second = first.next，完成三条连接后，first 成为本组尾节点，将 pre 移到 first 即可继续保持不变量。

解题步骤

创建 dummy -> head，令 pre = dummy。

只有 pre 后至少还有两个节点时才进入循环，落单节点保持原位。

记当前两节点为 first、second，按顺序连接：first.next = second.next、second.next = first、pre.next = second。

交换后 first 是本组尾节点，令 pre = first 处理下一组。

返回 dummy.next，它才是交换后的新头。

[1,2,3,4] 第一轮变为 dummy→2→1→3→4，第二轮变为 dummy→2→1→4→3。

代码实现

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;

        while (pre.next != null && pre.next.next != null) {
            ListNode first = pre.next;
            ListNode second = first.next;

            first.next = second.next;
            second.next = first;
            pre.next = second;
            pre = first;
        }
        return dummy.next;
    }
}

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    pre := dummy

    for pre.Next != nil && pre.Next.Next != nil {
        first := pre.Next
        second := first.Next

        first.Next = second.Next
        second.Next = first
        pre.Next = second
        pre = first
    }
    return dummy.Next
}

复杂度分析

时间复杂度：$O(n)$，每个节点只处理一次。

空间复杂度：$O(1)$，只使用常数个指针。

关键点总结

头节点可能变化时，用哨兵把头部操作统一成普通的“前驱接新头”。

三条连接的顺序不能乱：先让 first 接住下一组，避免后继链表丢失。

pre 始终指向已交换部分的尾部，交换后应移动到 first，而不是 second。

本题就是 K 个一组翻转在 k=2 时的特例，常见追问是推广到第 25 题。

易错点总结

只判断 pre.next != null：[1,2,3] 的最后一轮没有第二个节点，会空指针异常。

先执行 second.next = first：会覆盖原后继，再读取 second.next 时形成自环；必须先保存下一组连接。

交换后令 pre = second：pre 会停在组头，下一轮重复处理已交换节点；应移到组尾 first。

返回原 head：[1,2] 会从节点 1 开始，丢失新头节点 2；必须返回 dummy.next。

相似题目

题目	难度	考察点
25. K 个一组翻转链表	困难	本题的一般化，每 k 个一组整段反转再拼接
92. 反转链表 II	中等	只反转区间 `[left, right]`，前后断点重接
143. 重排链表	中等	找中点 + 反转后半 + 交替合并的组合操作
206. 反转链表	简单	三指针整链反转的基本功
234. 回文链表	简单	反转后半段与前半逐一比对，$O(1)$ 空间判回文
LCR 024. 反转链表	简单	206 的 LCR 镜像题
LCR 026. 重排链表	中等	143 的 LCR 镜像题
LCR 027. 回文链表	简单	234 的 LCR 镜像题
剑指 Offer 24. 反转链表	简单	206 的剑指 Offer 版本
面试题 02.06. 回文链表	简单	234 的面试金典版本
补充题 18. 反转双向链表	中等	双向链表 `prev`/`next` 两条指针同时互换