12 链表反转艺术：局部反转、k 组翻转与节点交换

链表反转艺术：局部反转、k 组翻转与节点交换

摘要

链表反转是面试中最高频的链表操作之一。理解反转的本质，才能应对各种变体题。本篇从反转整个链表的基础模板出发，逐步深入到局部反转（LeetCode 92，反转 m 到 n 段）、k 组翻转（LeetCode 25，每 k 个节点一组翻转，递归与迭代两种解法）和两两交换（LeetCode 24，k=2 的特例）。三道题形成完整的知识体系，掌握反转模板是关键。

---

第 1 章 反转链表：基础模板

在深入变体之前，先彻底掌握反转整个链表（LeetCode 206）的两种写法。

1.1 迭代反转

思路：用三个指针 prev、curr、next，逐节点翻转指向。

public ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    
    while (curr != null) {
        ListNode next = curr.next; // 暂存下一个节点（下一步 curr.next 要被改写）
        curr.next = prev;           // 反转：curr 指向前驱
        prev = curr;                // prev 前进
        curr = next;                // curr 前进
    }
    
    return prev; // curr==null 时，prev 是新头节点
}

逐步演示（[1,2,3,4,5]）：

初始: prev=null, curr=1

step1: next=2, 1.next=null, prev=1, curr=2
step2: next=3, 2.next=1, prev=2, curr=3
step3: next=4, 3.next=2, prev=3, curr=4
step4: next=5, 4.next=3, prev=4, curr=5
step5: next=null, 5.next=4, prev=5, curr=null

返回 prev=5（新头）→ 5→4→3→2→1→null ✓

1.2 递归反转

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head; // 基准情况
    
    ListNode newHead = reverseList(head.next); // 递归反转后面的链表
    head.next.next = head; // 后面节点的 next 反指向当前节点
    head.next = null;      // 当前节点的 next 清除（防止成环）
    
    return newHead;
}

递归的理解：reverseList(head.next) 已经把 head.next 之后的链表反转好了，返回了新头 newHead。此时 head.next 是反转后链表的末尾节点（它原来是第二个），我们只需让这个末尾节点指向 head，再把 head.next 置 null，即可完成。

---

第 2 章 LeetCode 92：反转链表 II

2.1 题目

LeetCode 92 - Reverse Linked List II（中等）

给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right，请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

位置从 1 开始计数。

输入: head = [1,2,3,4,5], left=2, right=4 → 输出: [1,4,3,2,5]
输入: head = [5], left=1, right=1          → 输出: [5]

2.2 “穿针引线”法

关键：局部反转的难点不在于反转本身（与反转整个链表相同），而在于反转完成后如何将两端重新连接。

需要保存 4 个”锚点”：

• pre：left 的前驱节点（反转段的左边界外一个）
• start：反转段的起始节点（第 left 个节点，反转后是新尾）
• then：当前准备反转的节点（遍历游标）
• end：反转段的末尾（第 right 个节点，反转后是新头）

哑节点的作用：当 left == 1 时，反转段从头节点开始，头节点本身也需要被反转，哑节点充当 pre。

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    
    // 找到 left-1 位置（反转段的前驱）
    ListNode pre = dummy;
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
    }
    
    // start 是反转段的第一个节点（反转后会成为尾节点）
    ListNode start = pre.next;
    // then 是当前要被"摘下来插到 pre 后面"的节点
    ListNode then = start.next;
    
    // 执行 right - left 次"头插"操作
    for (int i = 0; i < right - left; i++) {
        start.next = then.next;  // start 跳过 then
        then.next = pre.next;    // then 的 next 指向 pre 当前的后继（原反转段头部）
        pre.next = then;         // pre 的后继更新为 then（将 then 插到最前面）
        then = start.next;       // then 更新为下一个待处理节点
    }
    
    return dummy.next;
}

手动演示（[1,2,3,4,5], left=2, right=4）：

初始: dummy→1→2→3→4→5
pre=1（left-1=1步后）, start=2, then=3

第1次（i=0）:
  start.next = then.next = 4（2跳过3，2→4）
  then.next = pre.next = 2（3→2）
  pre.next = then = 3（1→3）
  then = start.next = 4
  状态: dummy→1→3→2→4→5

第2次（i=1）:
  start.next = then.next = 5（2跳过4，2→5）
  then.next = pre.next = 3（4→3）
  pre.next = then = 4（1→4）
  then = start.next = 5
  状态: dummy→1→4→3→2→5

结果: 1→4→3→2→5 ✓

直觉理解：每次循环把 start.next 的节点”摘下来插到 pre 后面”，相当于每次把反转段当前最右侧的节点移到最左侧，执行 right - left 次后，反转段就被翻转了。

复杂度：时间 $O(n)$，空间 $O(1)$。

---

第 3 章 LeetCode 25：K 个一组翻转链表

3.1 题目

LeetCode 25 - Reverse Nodes in k-Group（困难）

给你链表的头节点 head，每 k 个节点为一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

输入: head = [1,2,3,4,5], k = 2 → 输出: [2,1,4,3,5]
输入: head = [1,2,3,4,5], k = 3 → 输出: [3,2,1,4,5]

3.2 核心子问题的分解

关键观察：将 k 个一组翻转，分解为两个子问题：

1. 判断剩余节点 ≥ k：若不足 k 个节点，不翻转，直接返回
2. 翻转一组：对当前 k 个节点执行反转，返回新头节点和下一组的起点

3.3 迭代解法

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode prevGroupTail = dummy; // 上一组的最后一个节点
    
    while (true) {
        // 检查是否有 k 个节点可以翻转
        ListNode kth = getKthNode(prevGroupTail, k);
        if (kth == null) break; // 不足 k 个节点，不翻转
        
        ListNode nextGroupHead = kth.next; // 下一组的开始
        
        // 翻转 prevGroupTail.next 到 kth 这 k 个节点
        ListNode prev = nextGroupHead;
        ListNode curr = prevGroupTail.next;
        
        while (curr != nextGroupHead) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        // 此时 prev 是翻转后的新头，prevGroupTail.next 是翻转后的新尾
        
        // 连接：上一组尾部 → 新头（kth），新尾（prevGroupTail.next 原先指向的）已经指向 nextGroupHead
        ListNode newGroupHead = kth;   // kth 就是翻转后的新头
        ListNode newGroupTail = prevGroupTail.next; // 原来的组头，翻转后是组尾
        
        prevGroupTail.next = newGroupHead;
        prevGroupTail = newGroupTail;
    }
    
    return dummy.next;
}
 
// 从 node 出发，走 k 步，返回第 k 个节点；若不足 k 步则返回 null
private ListNode getKthNode(ListNode node, int k) {
    while (node != null && k > 0) {
        node = node.next;
        k--;
    }
    return node; // k==0 时 node 是第 k 个节点；若 k>0 时 node==null，返回 null
}

手动验证（[1,2,3,4,5], k=2）：

初始: dummy→1→2→3→4→5, prevGroupTail=dummy

第1轮:
  getKthNode(dummy, 2): dummy→1→2, 返回2（kth=2）
  nextGroupHead=3
  翻转 1→2（prev从3开始）:
    curr=1: next=2, 1.next=3, prev=1, curr=2
    curr=2: next=3, 2.next=1, prev=2, curr=3（curr==nextGroupHead，停止）
  新头=2, 新尾=1（1.next=3）
  prevGroupTail(dummy).next = 2
  prevGroupTail = 1
  链表: dummy→2→1→3→4→5

第2轮:
  getKthNode(1, 2): 1→3→4, 返回4（kth=4）
  nextGroupHead=5
  翻转 3→4:
    curr=3: next=4, 3.next=5, prev=3, curr=4
    curr=4: next=5, 4.next=3, prev=4, curr=5（停止）
  新头=4, 新尾=3（3.next=5）
  prevGroupTail(1).next = 4
  prevGroupTail = 3
  链表: dummy→2→1→4→3→5

第3轮:
  getKthNode(3, 2): 3→5→null, k=1 时 node=null, 返回 null
  break

返回 2→1→4→3→5 ✓

3.4 递归解法（代码更简洁）

public ListNode reverseKGroup(ListNode head, int k) {
    // 检查是否有 k 个节点
    ListNode node = head;
    for (int i = 0; i < k; i++) {
        if (node == null) return head; // 不足 k 个，不翻转，直接返回
        node = node.next;
    }
    // node 现在是第 k+1 个节点（下一组的起点）
    
    // 递归处理后续部分
    ListNode nextGroupHead = reverseKGroup(node, k);
    
    // 反转当前 k 个节点
    ListNode prev = nextGroupHead;
    ListNode curr = head;
    for (int i = 0; i < k; i++) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    // prev 是翻转后的新头，head 是翻转后的新尾（已指向 nextGroupHead）
    return prev;
}

递归版本的核心思路：先递归处理第 k+1 个节点之后的部分，拿到下一组处理后的头节点 nextGroupHead，再反转当前 k 个节点，末尾节点（head）自动连接到 nextGroupHead。

复杂度：时间 $O(n)$，空间 $O(n/k)$（递归栈）。

---

第 4 章 LeetCode 24：两两交换链表中的节点

4.1 题目

LeetCode 24 - Swap Nodes in Pairs（中等）

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

输入: head = [1,2,3,4] → 输出: [2,1,4,3]
输入: head = [1]       → 输出: [1]

4.2 方法一：迭代

这是 k=2 的 k 组翻转特例，直接写出高效的迭代解法：

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode prev = dummy;
    
    while (prev.next != null && prev.next.next != null) {
        ListNode first = prev.next;
        ListNode second = prev.next.next;
        
        // 执行交换
        first.next = second.next; // first 跳过 second
        second.next = first;       // second 指向 first
        prev.next = second;        // prev 指向新的头（second）
        
        // prev 移动到 first（交换后 first 是这对节点的尾部）
        prev = first;
    }
    
    return dummy.next;
}

手动验证（[1,2,3,4]）：

初始: dummy→1→2→3→4, prev=dummy

第1轮: first=1, second=2
  1.next = 3（first 跳过 second）
  2.next = 1（second 指向 first）
  dummy.next = 2（prev 指向 second）
  prev = 1
  链表: dummy→2→1→3→4

第2轮: first=3, second=4
  3.next = null
  4.next = 3
  1.next = 4（prev.next）
  prev = 3
  链表: dummy→2→1→4→3

返回 2→1→4→3 ✓

4.3 方法二：递归（一行核心逻辑）

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head;
    
    ListNode second = head.next;
    head.next = swapPairs(second.next); // 递归处理后续部分
    second.next = head;                  // second 指向 head
    
    return second; // second 成为新头
}

递归解法极简：head 和 second 交换，head.next 连接递归处理后续的结果，second 变为新头。

---

第 5 章 反转链表的知识体系

5.1 反转的本质操作

无论哪种反转变体，核心都是这个三步操作（迭代版）：

ListNode next = curr.next;  // 暂存
curr.next = prev;            // 反转
prev = curr; curr = next;    // 移动

变体题的不同点在于：

• 反转哪段：206 反转全部，92 反转 m 到 n，25 反转每组 k 个
• 如何衔接两端：反转完成后，如何把左侧链表尾和右侧链表头正确连接

5.2 三道题的关系

          206 反转整个链表（基础）
               ↓
    92 反转 m 到 n（局部版本）
               ↓
  25 k 组翻转（重复多次局部反转）
               ↓
     24 两两交换（k=2 特例）

理解了 206，其余三道都是扩展。

5.3 面试技巧

场景	建议
LeetCode 92	先画图标注 pre、start、then，代码前确认 4 个锚点
LeetCode 25	递归版本代码简洁，但要能解释递归的含义；迭代版本更稳健
LeetCode 24	递归版本是展示简洁代码能力的好机会，但也要能写迭代版本

---

下一篇预告

13 链表综合运用：大数加法、重排链表、随机指针与 LRU 缓存 是本系列的收官篇。LeetCode 2（大数加法）是进位模拟；LeetCode 143（重排链表）综合运用了找中点、反转和合并；LeetCode 138（复制带随机指针的链表）考察对链表结构的深度理解；LeetCode 146（LRU 缓存）是数组链表系列的终极考题，考察 HashMap + 双向链表的工程实现能力，是大厂面试的常客。