链表区间反转终极指南：从牛客157题到面试实战

一、问题描述

牛客网第157题要求实现单链表中指定区间[m,n]内节点的反转，要求空间复杂度O(1)，且只能遍历链表一次。这是面试高频题型，考察指针操作和边界处理能力。

二、算法核心解析

1. 虚拟头节点技巧：避免处理头节点特殊情况

2. 四指针操作法：

• pre：始终指向区间前驱节点

• cur：当前待反转节点的前一个节点

• tmp：待插入节点（每次将cur->next插入到pre后）

3. 时间复杂度：O(n)，只需一次遍历

4. 空间复杂度：O(1)

三、边界测试用例

1. 整个链表反转（m=1, n=length）

2. 单个节点反转（m=n）

3. 头节点反转（m=1）

4. 尾节点反转（n=length）

二、C++实现代码（带详细注释）

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummy(-1); // 虚拟头节点简化边界处理
        dummy.next = head;
        ListNode *pre = &dummy;
        
        // Step1: 定位到m-1位置
        for (int i = 1; i < m; ++i) {
            pre = pre->next;
        }
        
        // Step2: 反转m到n区间
        ListNode *cur = pre->next;
        for (int i = m; i < n; ++i) {
            ListNode *tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = pre->next;
            pre->next = tmp;
        }
        
        return dummy.next;
    }
};

五、总结

1.为什么链表反转是面试必考题？

链表操作能直接体现程序员的编码基本功，区间反转更是考察：

• 指针操作的精确性

• 边界条件的处理能力

• 代码的鲁棒性设计

2.高频变种题型

1. 每k个节点一组反转

2. 交替反转链表

3. 反转链表指定节点

3.性能优化要点

1. 使用虚拟头节点统一操作逻辑

2. 保持pre指针不动，通过修改next指针实现反转

3. 循环终止条件选择i < n而非i <= n避免多余操作

4.常见错误警示

1. 忘记处理m=1的情况

2. 反转后未正确连接首尾节点

3. 循环次数计算错误导致部分反转