反转链表 II

题目

题目来源：力扣（LeetCode）

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

示例 1：

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

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

思路分析

1、首先，我们定义一个虚拟头节点，起名叫做 hair，将它指向我们的真实头节点
2、然后定义一个 prev 指针，将其指向虚拟头节点
3、我们再定义一个 curr 指针，将其指向 prev 指向所指向节点的下一个节点
4、让我们的 prev 指针和 curr 指针同时向后移动，直到我们找到了待反转位置的第一个节点，此时我们的 curr 指针指向节点2，即待反转位置的第一个节点。
5、此时，我们再定义两个指针，con 和 tail，其中 con 指向 prev 所指向的节点，tail 指向 curr 所指向的节点。con 所指向的节点，将是我们将部分链表反转后，部分链表 头节点的前驱结点，tail 则是部分链表 反转后的尾节点。
6、开始我们的链表反转，首先定义一个 third 指针指向 curr 所指向节点的下一个节点，然后将 curr 所指向的节点的 next 指针域指向 prev 所指向的节点：
接下来将 prev 指针移动到 curr 指针所在的位置，将 curr 指针移动到 third 指针所在的位置，同时 third 指针也是往后移动，指向当前 curr 指针所指向节点的下一个节点，然后将curr 指针所指向的节点的next指针域指向 prev 所指向的节点：

7、不断地往后移动 prev、curr、third 指针，直到 prev 指针指向待翻转链表的最后一个节点，此时位置 left 到位置 right 的链表节点完成了反转。

8、最后，我们将 con 指针所指向的节点的 next 指针域 指向 prev 指针所指向的节点，将 tail 指针所指向的节点的 next 指针域指向 curr 所指向的节点，至此，我们完成了链表的反转，并将链表的所有节点连接了起来。

var reverseBetween = function (head, left, right) {
  if (!head) return null;
  let ret = new ListNode(-1, head), pre = ret, cnt = right - left + 1;
  while (--left) {
    pre = pre.next;
  }
  pre.next = reverse(pre.next, cnt)
    return ret.next;
  };
  var reverse = function (head, n) {
    let pre = null, cur = head;
    while (n--) {
    [cur.next, pre, cur] = [pre, cur, cur.next];
  }
  head.next = cur;
  return pre;
}