反转链表 II

1. 问题描述和示例

问题描述

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

示例

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
解释：反转第2到第4个节点

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]
解释：只有一个节点，无需反转

示例 3：

输入：head = [1,2], left = 1, right = 2
输出：[2,1]
解释：反转整个链表

2. 核心难点分析

主要难点

1. 指定区间反转：只反转指定位置的节点，而不是整个链表
2. 边界处理：处理 left=1（从头开始）和 right=n（到尾结束）的情况
3. 指针操作：需要维护多个指针来完成局部反转
4. 连接处理：反转后需要正确连接前后部分

关键要点

• 需要找到反转区间的前一个节点
• 反转过程中要保存反转区间的第一个和最后一个节点
• 反转完成后要正确连接三个部分：前部分 + 反转部分 + 后部分

3. 多种解法对比

解法一：一次遍历法（推荐）

• 思路：使用虚拟头节点，一次遍历完成反转
• 优点：代码简洁，易于理解
• 缺点：需要额外的虚拟节点

解法二：递归法

• 思路：递归处理反转逻辑
• 优点：代码优雅
• 缺点：空间复杂度较高，可能栈溢出

解法三：迭代法

• 思路：先找到反转区间，再进行迭代反转
• 优点：空间复杂度最优
• 缺点：代码相对复杂

4. 详细Java代码实现

链表节点定义

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

解法一：一次遍历法

public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 创建虚拟头节点，简化边界处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // 找到反转区间的前一个节点
        ListNode prev = dummy;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        
        // 反转区间的第一个节点
        ListNode curr = prev.next;
        
        // 执行反转操作 (right - left) 次
        for (int i = 0; i < right - left; i++) {
            ListNode next = curr.next;
            curr.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        
        return dummy.next;
    }
}

解法二：递归法

public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    
    // 反转链表前N个节点
    private ListNode successor = null;
    
    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
}

解法三：迭代法

public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        
        // 移动到反转区间的前一个节点
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }
        
        // 反转区间的起始节点
        ListNode start = pre.next;
        ListNode then = start.next;
        
        // 执行反转
        for (int i = 0; i < right - left; i++) {
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }
        
        return dummy.next;
    }
}

5. 测试用例和预期结果

测试用例

public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // 测试用例1：正常情况
        ListNode head1 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result1 = solution.reverseBetween(head1, 2, 4);
        printList(result1); // 预期输出：[1, 4, 3, 2, 5]
        
        // 测试用例2：单节点
        ListNode head2 = createList(new int[]{5});
        ListNode result2 = solution.reverseBetween(head2, 1, 1);
        printList(result2); // 预期输出：[5]
        
        // 测试用例3：反转整个链表
        ListNode head3 = createList(new int[]{1, 2});
        ListNode result3 = solution.reverseBetween(head3, 1, 2);
        printList(result3); // 预期输出：[2, 1]
        
        // 测试用例4：从头开始反转
        ListNode head4 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result4 = solution.reverseBetween(head4, 1, 3);
        printList(result4); // 预期输出：[3, 2, 1, 4, 5]
        
        // 测试用例5：到尾结束反转
        ListNode head5 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result5 = solution.reverseBetween(head5, 3, 5);
        printList(result5); // 预期输出：[1, 2, 5, 4, 3]
    }
    
    // 辅助方法：创建链表
    private static ListNode createList(int[] nums) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        for (int num : nums) {
            curr.next = new ListNode(num);
            curr = curr.next;
        }
        return dummy.next;
    }
    
    // 辅助方法：打印链表
    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
}

6. 边界情况处理

关键边界情况

1. left = 1：从头节点开始反转
2. right = n：反转到链表末尾
3. left = right：只有一个节点，无需反转
4. 链表为空：直接返回null
5. 链表只有一个节点：返回原链表

边界处理技巧

// 边界检查
if (head == null || head.next == null || left == right) {
    return head;
}

// 使用虚拟头节点处理left=1的情况
ListNode dummy = new ListNode(0);
dummy.next = head;

7. 相关题目

类似题目

1. 206. 反转链表：反转整个链表
2. 25. K个一组翻转链表：每K个节点反转一次
3. 61. 旋转链表：将链表向右旋转k个位置
4. 24. 两两交换链表中的节点：相邻节点两两交换
5. 143. 重排链表：将链表重新排列

题目关联

• 反转链表II是反转链表的进阶版本
• 掌握了反转链表II，K个一组翻转链表就容易理解
• 都涉及链表的局部操作和指针处理

8. 复杂度分析

时间复杂度

• 一次遍历法：O(n)，其中n是链表长度
• 递归法：O(n)，递归调用栈深度为n
• 迭代法：O(n)，需要遍历链表

空间复杂度

• 一次遍历法：O(1)，只使用常数额外空间
• 递归法：O(n)，递归调用栈空间
• 迭代法：O(1)，只使用常数额外空间

最优解选择

推荐使用一次遍历法，因为：

• 时间复杂度最优：O(n)
• 空间复杂度最优：O(1)
• 代码简洁易懂
• 处理边界情况方便

9. 面试要点总结

核心考点

1. 指针操作技巧：如何维护多个指针
2. 边界条件处理：left=1和right=n的特殊情况
3. 虚拟头节点：简化边界处理的常用技巧
4. 局部反转：在不影响其他部分的情况下反转指定区间

面试回答要点

1. 分析问题：明确需要反转的区间和保持不变的部分
2. 选择方法：推荐一次遍历法，说明原因
3. 处理边界：重点说明如何处理特殊情况
4. 代码实现：写出清晰的代码并添加注释
5. 测试验证：给出几个测试用例验证正确性

常见面试问题

• 如何处理left=1的情况？
• 为什么要使用虚拟头节点？
• 如何确保反转后的连接正确？
• 能否优化空间复杂度？

10. 性能优化技巧

优化策略

1. 提前终止：如果left=right，直接返回
2. 虚拟头节点：统一处理边界情况
3. 一次遍历：避免多次遍历链表
4. 指针复用：减少临时变量的使用

代码优化

public ListNode reverseBetween(ListNode head, int left, int right) {
    // 提前终止优化
    if (head == null || left == right) {
        return head;
    }
    
    // 使用虚拟头节点统一处理
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    
    // 一次定位到反转起点
    for (int i = 0; i < left - 1; i++) {
        prev = prev.next;
    }
    
    // 高效反转
    ListNode curr = prev.next;
    for (int i = 0; i < right - left; i++) {
        ListNode next = curr.next;
        curr.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }
    
    return dummy.next;
}

性能对比

方法	时间复杂度	空间复杂度	代码复杂度	推荐度
一次遍历法	O(n)	O(1)	中等	⭐⭐⭐⭐⭐
递归法	O(n)	O(n)	简单	⭐⭐⭐
迭代法	O(n)	O(1)	复杂	⭐⭐⭐⭐

总结

反转链表II是链表操作中的经典问题，核心在于：

1. 理解局部反转的概念
2. 掌握指针操作技巧
3. 正确处理边界情况
4. 选择合适的算法实现

通过这道题可以深入理解链表的指针操作，为解决更复杂的链表问题打下基础。建议多练习相关题目，熟练掌握各种链表操作技巧。