反转链表II

LeetCode-92

// 头插法，参考：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/java-shuang-zhi-zhen-tou-cha-fa-by-mu-yi-cheng-zho/

// 时间复杂度：O(N)，其中 N 是链表总节点数。最多只遍历了链表一次，就完成了反转
// 空间复杂度：O(1)，只使用到常数个变量

var reverseBetween = function(head, left, right) {
  // 虚拟头节点，用于存储头节点，用于返回结果
  let dummyHead = new ListNode()
  dummyHead.next = head
  // 守卫指针
  let guard = dummyHead
  // 移动指针
  let move = dummyHead.next
  // 需要移动到的目标位置次数
  let MoveCount = left - 1
  // 移动节点
  while(MoveCount--) {
    guard = guard.next
    move = move.next
  }
  // console.log(guard.val, move.val)

  // 需要执行头插法的次数
  let changeCount = right - left
  while(changeCount--) {
    // 删除首个节点的
    let removeNode = move.next
    move.next = removeNode.next
    
    // 头插法：移除后的节点插入到守卫节点后面位置【注意：这里guard.next不能写成move节点，不然每次循环都会把上一个指向丢掉】
    removeNode.next = guard.next
    guard.next = removeNode // guard.next节点永远指向移动指针节点或删除后插入的节点(供下一轮插入的节点链接使用)
  }
  return dummyHead.next
}