每日算法随笔：反转链表 II

明白了！下面我将基于你给的两种方法来详细解释题解，并展示每一步的变化过程。

题解：反转链表 II

这道题要求我们反转链表中从第 left 个节点到第 right 个节点的部分，返回反转后的链表。我们会使用两种方法：递归 和 迭代。

示例解析

• 示例 1：
  输入：head = [1, 2, 3, 4, 5], left = 2, right = 4
  输出：[1, 4, 3, 2, 5]

  在这个例子中，链表 [1, 2, 3, 4, 5] 中，需要反转位置 2 到 4 的节点，最终得到 [1, 4, 3, 2, 5]。

• 示例 2：
  输入：head = [5], left = 1, right = 1
  输出：[5]

  单个节点的链表，不需要反转，直接返回原链表。

解法 1：迭代法

迭代法通过调整链表中的指针，逐步实现反转目标区间的节点。

步骤

1. 初始化虚拟节点：创建一个 dummy 节点指向链表头部，方便处理 left 在第一个节点的情况。
2. 找到 left 前的节点：通过遍历找到第 left 个节点之前的节点 pre。
3. 反转链表区间：通过调整节点的 next 指针，依次反转区间内的节点。
4. 返回结果：最后返回 dummy.next，即反转后的链表。

代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 创建虚拟节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // 找到 left 前面的节点
        ListNode pre = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        
        // 开始反转区间
        ListNode curr = pre.next;
        ListNode next = null;
        for (int i = 0; i < right - left; i++) {
            next = curr.next;
            curr.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        
        return dummy.next;
    }
}

示例变化过程

1. 初始化：创建虚拟节点 dummy，并找到 left 之前的节点 pre，即 pre = 1。

   初始链表: [1 -> 2 -> 3 -> 4 -> 5]
   

2. 第一次反转：

   • 当前 curr = 2，next = 3。
   • 将 next 节点插入到 pre 后面。

   反转后: [1 -> 3 -> 2 -> 4 -> 5]
   

3. 第二次反转：

   • 当前 curr = 2，next = 4。
   • 将 next 节点插入到 pre 后面。

   最终结果: [1 -> 4 -> 3 -> 2 -> 5]
   

解法 2：递归法

递归法的核心思想是逐步缩小反转范围，最终通过递归栈返回反转后的子链表。

步骤

1. 递归终止条件：当 left == 1 时，调用反转前 right 个节点的函数。
2. 递归：每次向下递归，直到找到第 left 个节点，然后开始反转前 right-left+1 个节点。
3. 返回结果：通过递归调用栈反转链表，并将各部分重新连接。

代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 当left == 1时，调用反转前right个节点的函数
        if (left == 1) {
            return reverseN(head, right);
        }
        // 递归前进到left - 1的位置
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    
    // 反转前n个节点的子函数
    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            return head;
        }
        ListNode newHead = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

示例变化过程

1. 递归调用：

   • 第一次递归：left = 2, right = 4，递归调用 head = 2。
   • 第二次递归：left = 1, right = 3，开始反转前 3 个节点。

2. 第一次反转：

   • 反转 [2 -> 3 -> 4] 中前 3 个节点，得到 [4 -> 3 -> 2]。

   反转后: [1 -> 4 -> 3 -> 2 -> 5]
   

3. 返回结果：递归结束后，返回完整的反转链表 [1 -> 4 -> 3 -> 2 -> 5]。

总结

• 迭代法：通过调整指针逐步反转目标区间，时间复杂度为 O(n)，只需一趟扫描链表。
• 递归法：利用递归栈反转链表，代码简洁，但可能会带来栈空间的额外开销。

两种方法在解决这类链表局部反转的问题时都很高效，选择使用哪种方法可以根据实际需求和个人习惯。