3. 反转链表的一部分

看下力扣第 92 题「 反转链表 II 」：

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

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

注意这里的索引是从 1 开始的。迭代的思路大概是：先用一个 for 循环找到第 m 个位置，然后再用一个 for 循环将 m 和 n 之间的元素反转。但是我们的递归解法不用一个 for 循环，纯递归实现反转。

迭代实现思路看起来虽然简单，但是细节问题很多的，反而不容易写对。相反，递归实现就很简洁优美，下面就由浅入深，先从反转整个单链表说起。

首先，如果 m == 1，就相当于反转链表开头的 n 个元素嘛，也就是我们刚才实现的功能：

ListNode reverseBetween (ListNode head, int m, int n) {
    // base case
    If (m == 1) {
        // 相当于反转前 n 个元素
        Return reverseN (head, n);
    }
    // ...
}

如果 m != 1 怎么办？如果我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head.next.next 呢……

区别于迭代思想，这就是递归思想，所以我们可以完成代码：

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

递归魔法：反转单链表 | labuladong 的算法笔记

值得一提的是，递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼，但是考虑效率的话还是使用迭代算法更好。

 public ListNode reverseBetween (ListNode head, int m, int n) {
 
        // write code here
 
        //设置虚拟头节点
 
        ListNode dummy = new ListNode(-1);
 
        dummy.next = head;
 
  
 
        ListNode pre = dummy;
 
        ListNode cur = head;
 
  
 
        for(int i = 1;i<m;i++){
 
             pre = pre.next;
 
            cur = cur.next;
 
        }
 
  
 
        ListNode temp = null;
 
        // 使用一个额外的节点，用于记录链表反转后的尾部
 
        ListNode tail = cur;
 
  
 
        for(int i = m;i<=n;i++){
 
             ListNode next = cur.next;
 
            cur.next = temp;
 
            temp = cur;
 
            cur = next;
 
        }
 
          // 更新前后连接
 
         pre.next = temp;
 
         tail.next = cur;
 
  
  
  
 
        return dummy.next;
 
    }