92.反转链表 II

题目描述

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

解题思路

思路一

• 遍历链表，在没有到达指定反转位置时，继续遍历，直到到达指定反转位置
• 达到指定反转位置时，记录当前节点，并开始反转
• 反转过程中将在反转范围中的下一个节点（当前正在处理的节点）指向反转后头结点的下一个节点，并更新反转后头结点的下一个节点为当前节点
• 反转结束后，将进入反转节点前的一个节点执行反转链表的头节点，并将反转节点的尾结点指向当前处理的节点
• 继续遍历后续节点，直到链表遍历结束

var reverseBetween = function (head, left, right) {
  if (!head) return null

  let newHead = {}
  let prev = newHead
  let current = head
  let i = 1 // 当前节点位置

  let reverseHead = {}
  let reverseTail = {}

  while (current) {
    if (i >= left && i <= right) {
      if (reverseHead.next) {
        let next = current.next

        current.next = reverseHead.next
        reverseHead.next = current
        current = next
      } else {
        reverseHead.next = current
        reverseTail.next = current
        current = current.next
      }

      i++
      continue
    }

    if (reverseHead.next) {
      prev.next = reverseHead.next
      reverseTail.next.next = current
      reverseHead.next = null // 标识已经处理
    } else {
      prev.next = current
    }

    prev = current
    current = current.next
    i++
  }

  if (reverseHead.next) {
    prev.next = reverseHead.next
    reverseTail.next.next = current
  }

  return newHead.next
}

思路二

• 遍历链表，在没有到达指定反转位置时，继续遍历，直到到达指定反转位置
• 达到指定反转位置时，记录当前节点，继续遍历
• 反转过程中，每次将反转范围内当前正在处理的节点插入到反转链表的头结点之前
• 退出反转范围时，将反转范围的未节点执行当前正在处理的节点
• 继续遍历后续节点，直到链表遍历结束

var reverseBetween = function (head, left, right) {
  if (!head) return null

  let newHead = {}
  let prev = newHead
  let current = head
  let i = 1 // 当前节点位置
  let reverseHead = null
  let reverseTail = null

  while (current) {
    if (i >= left && i <= right) {
      if (!reverseHead) {
        reverseHead = current
        reverseTail = current
        prev.next = current
        current = current.next
      } else {
        let next = current.next

        prev.next = current
        current.next = reverseHead
        reverseHead = current
        current = next
      }

      i++
      continue
    }

    if (reverseTail) {
      reverseTail.next = current
      reverseTail = null
    } else {
      prev.next = current
    }

    prev = current
    current = current.next
    i++
  }

  if (reverseTail) {
    reverseTail.next = current
  }

  return newHead.next
}

参考

• 92. 反转链表 II (opens new window)