链表:截取从n到m的链表（leetcode92）

题目描述:反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

https://leetcode-cn.com/problems/reverse-linked-list-ii/

说明:
1 ≤ m ≤ n ≤ 链表长度。

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

---

image.png

解题思路：其实也是一种反转链表，只是截取一段链表反转后插回去原来的链表。利用循环法或者递归法都可以。因此区别只是记录一下关键节点而已。

假设此时m = 2, n=4,那么就是截取2->3->4，反转后1->4,然后2->5

所以我们要记录前置节点1，preStartNode

而且还要记录开始反转的节点2，startNode,为什么呢？

因为单链表是单向的，无法返回，那么反转到最后，我们的head是节点4，而我们需要节点2的next指向5，所以也要记录第一个节点

而为什么不用记录最后一个节点呢？因为遍历到最后，我们的pre节点就是最后一个节点4，cur就是节点5，所以不用记录（相当于最后一个遍历指针）

为什么要使用一个哨兵dummyHead呢？
因为返回反转后的链表后，要插入原来preStartNode之后，如果是从第一个开始反转，就没有preStartNode了，所以这样我们就简化了

image.png

var reverseBetween = function(head,m,n){
  let p = dummyNode = new ListNode()
  let count = n - m
  //反转链表的前一个
  let preStart,
   //开始反转的第一个节点
      startNode,
    //反转指针
      pre,
      cur
  //让p和dummyNode连接head
  p.next = head
  for(let i=0;i<m-1;i++){
    p = p.next
  }
  preStartNode = p
  startNode = pre = p.next
  cur = pre.next
  for(let i=0;i<count;i++){
    let temp = cur.next
    cur.next = pre
    pre = cur
    cur = temp
  }
  preStartNode.next = pre
  startNode.next = cur
  return dummyNode.next
}

附上codepen地址

以上~~