LeetCode题解：92. 反转链表 II，递归，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/

解题思路：

1. 该题实际只要求翻转链表的值，无需真实反转每个节点。
2. 利用递归遍历链表，从位置1遍历到n，再逐层退出。
3. 使用两个指针，分别指向需要反转的链表两端。
4. 递归下探的时候，将左指针移动到m位置，右指针移动到n位置。
5. 在递归退出的时候，每次递归右指针都会依次从位置n移动回到位置1，此时只需要在从n到m回退的过程中，交换左右指针对应的值即可。
6. 需要注意的是，右指针从n到m回退时，左指针此时都会停留在m，每次递归需要主动将左指针向前移动一次。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
  let left = head // 起始时左指针指向头结点
  let reverse = true // 标识递归是否可以继续进行

  // 递归进行链表的反转
  function recursion(right, m, n) {
    // 递归终止条件
    // 由于每次递归都会将n减1，因此n等于1时，表示已递归了n-1次
    // 此时表示右指针已被移动了m-1次，它已在n位置
    if (n === 1) {
      return
    }

    // 递归下探时，移动两个指针到翻转的起始位置
    // 每次递归都将右指针向前移动一次，当递归终止时，它会停在第n个节点，此时可以开始反转
    right = right.next
    n--

    // 由于每次递归都会将m减1，当左指针被移动m-1次时，左指针已被移动到了第m个节点，此时停止移动
    if (m > 1) {
      left = left.next
      m--
    }

    // 递归下探一层
    recursion(right, m, n)

    // 递归退出时，进行链表反转操作
    // 判断链表反转操作是否可以停止
    if (
      // 当m到n为奇数个节点时，反转完成后两个指针会相遇
      left === right ||
      // 当m到n为偶数个节点时，反转完成后右指针会移动到左指针之前，即为right.next指向了左指针
      right.next === left
    ) {
      // 由于递归会继续向外进行，因此必须用变量标识是否可以反转，否则
      reverse = false
    }

    // 如果反转可以进行，则将左右指针的值对调，完成翻转操作
    if (reverse) {
      const temp = left.val
      left.val = right.val
      right.val = temp
      // 在递归退出的时候，右指针自然会在每一层递归时它所处的位置，因此不需要主动移动右指针
      // 但在右指针从n回退到m的过程中，左指针原本一直停留在m位置
      // 因此每次反转后，都必须主动移动左指针，否则左指针将保持不变
      // 同时因为这里需要移动左指针，如果左指针通过递归传参，则会随着每次递归而变动，因此需要用一个全局变量保存
      left = left.next
    }
  }
  // 起始时右指针指向头结点
  recursion(head, m, n)

  // 完成反转后，链表的头结点不变，直接返回链表即可
  return head
};