92.反转链表||.md

LeetCode-92 反转链表 II

难度： 中等

类型： 链表

题目：

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

示例:

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

思路：

todo

实现：

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 leftHead, cur, pre = null 
  // 空结点
  let dummy = new ListNode()
  dummy.next = head
  // 创建一个游标 用于遍历
  let p = dummy

  // 找到有效链表（head）的头部结点
  for (let i = 0; i < m - 1; i++) {
    p = p.next
  }
  // 缓存头部结点
  leftHead = p
  // 找到指定的反转区间的头部结点
  let start = p.next
  // pre 指向 start 
  pre = start 
  // cur 指向 pre 后一个结点
  cur = pre.next

  // 开始局部反转指定区间的链表 
  for (let i = m; i < n; i++) {
    // 保存 cur 后一个结点
    let next = cur.next
    // 反转指针
    cur.next = pre
    // pre 前进一步
    pre = cur
    // cur 前进一步
    cur = next
  }

  // 局部反转完后，要建立链表的链接关系

  // head头部结点下一个指针要指向pre
  leftHead.next = pre

  // start的下一个结点（反转区间的头部结点，反转后跑到反转区间的最后一个）要指向cur
  start.next = cur

  // 最后将head返回
  return dummy.next
}