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

/**
 * 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
};