基于这个链表的数据结构来实现链表的反转
链表 Link-list

反转整个链表

class LinkedList {
  // ...
  reverse(head = this.head) {
    const reverse = (head) => {
      if (head.next == null) return head; // 当 next 为 null 返回这个节点，即最后的节点 last
      const last = reverse(head.next);
      // 反转指向，eg. 1 -> 2 -> null => 2 -> 1 -> null
      head.next.next = head; 
      head.next = null;
      return last;
    }
    this.head = reverse(head); // 把反转后的 last 指回链表的 head，就能让链表访问正常
  }
}

对于递归算法，最重要的就是明确递归函数的定义

reverse 函数的定义：
输入一个节点 head，将“以 head 为起点”的链表反转，并返回反转之后的头节点
使用 reverse(head) 后，会进行递归：
const last = this.reverse(head.next);
根据 reverse 函数的定义，this.reverse(head.next) 执行完后整个链表变成了：

reverse 函数会返回反转之后的头节点，我们用变量 last 来接收
head.next.next = head;
this.head = last; 把链接的 head 指为反转后的头节点
head.next = null;
return last;
:::warning
递归数要有 base case
if (head.next == null) return head;
意思是如果链表只有一个节点的时候反转也是它自己，直接返回即可。

当链表递归反转之后，新的头节点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null：
head.next = null; :::

反转链表前 N 个节点

将链表的前 n 个节点反转 (n <= 链表长度) reverseN(n);
如 reverseN(3)：

实现思路和反转整个链表差不多，只要稍加修改：

class LinkedList {
// ...  
reverseN(n) {
 // 后驱节点
 let successor = null;
 // 反转以 head 为起点的 n 个节点，返回新的头节点
 const reverseN = (head, n) => {
   if (n == 1) {
     // 记录第 n + 1 个节点
     successor = head.next;
     return head;
   }
   // 以 head.next 为起点，需要反转前 n - 1 节点
   const last = reverseN(head.next, n -1);
   head.next.next = head;
   // 让反转之后的 head 节点和后面的节点连起来
   head.next = successor;
   return last;
 }
 this.head = reverseN(this.head, n); // 把反转后的 last 指回链表的 head，就能让链表访问正常
}
}

具体区别：

base case 变成 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。
反转整个链表时把 head.next 设置为 null，因为整个链表反转后原来的 head 变成整个链表的最后一个节点。
但现在 head 节点在递归反转之后不一定是最后一个节点，所以要记录后驱 successor（第 n+1 个节点），反转之后将 head 连接上。

反转链表的一部分

给一个索引区间 [m,n]（索引从 1 开始），仅仅反转区间中的链表元素。reverseBetween(m, n);

如果 m === 1，就相当于反转链表开头的 n 个元素，也就是上面的反转链表前N个节点实现
如果 m != 1 怎么办？
如果把 head.next 的索引视为 1，就是从第 m 个元素开始反转。
那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始；
那么对于 head.next.next 呢…

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

class LinkedList {
  // ...
  reverseBetween(m, n) {
    // 后驱节点
    let successor = null;
    // 反转以 head 为起点的 n 个节点，返回新的头节点
    const reverseN = (head, n) => {
      if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
      }
      // 以 head.next 为起点，需要反转前 n - 1 节点
      const last = reverseN(head.next, n - 1);
      head.next.next = head;
      // 让反转之后的 head 节点和后面的节点连起来
      head.next = successor;
      return last;
    }
    const reverseBetween = (head, m, n) => {
      // base case
      if (m == 1) {
        return reverseN(head, n);
      }
      // 前进到反转的起点触发 base case
      head.next = reverseBetween(head.next, m - 1, n - 1);
      return head;
    }
    this.head = reverseBetween(this.head, m, n);
  }
}

总结

处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。
处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题。

链表反转

反转整个链表

反转链表前 N 个节点

反转链表的一部分

总结