Lt92. 反转链表 II

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路

结合206. 反转链表的思路。将链表分割成三部分，头部尾部以及需要翻转的部分。

1. 使用 dummy 哑结点解决 m=1 的情况。首先进行一部分遍历，temp 为遍历的指针，直到当前 temp 节点的 next 为需要翻转节点的首节点。
2. 再使用一个 cur 作为临时指针。此时问题就转化成了206. 反转链表，但是不需要完全翻转，只需要翻转 n-m+1 个元素即可，所以使用 for 再进行一次遍历，遍历次数为 n-m+1 次。例如1->2->3->4->5->6->NULL, m = 2, n = 4这个用例，temp 为1->2->3->4->5->6->NULL，cur 为2->3->4->5->6->NULL，对 4-2+1 三个元素：2、3、4 进行反转。建立一个 prev 作为记录上一个节点的指针，初始指向 null，执行以下过程。
   1. 先使用nextTemp记录cur.next
   2. cur.next指向prev
   3. prev指向cur
   4. cur指向nextTemp
3. 执行完以上过程之后，会将链表划分为三段。prev指向已经翻转完毕的链表的开始4->3->2->NULL，cur 指向剩余的尾部链表5->6->NULL。因为修改过 2 的指向，所以temp会变成1->2->NULL。
4. 现在要修改指向，2 的 next 应该指向尾部，1 的 next 应该指向翻转完毕链表。所以temp.next.next指向cur，temp.next指向prev，即可将三段重新拼接成一条链表。

解答

/**
 * 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) {
  const dummy = new ListNode();
  dummy.next = head;
  let temp = dummy;
  let tail = null;
  for (let i = 1; i < m; i++) temp = temp.next;
  let prev = null;
  let cur = temp.next;
  for (let i = 0; i < n - m + 1; i++) {
    const nextTemp = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nextTemp;
  }
  temp.next.next = cur;
  temp.next = prev;
  return dummy.next;
};