Skip to main content

反转链表 II

92. 反转链表 II

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

示例 1:

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2:

输入：head = [5], left = 1, right = 1
输出：[5]

代码

思路：

虚拟头节点
截取反转区域，置为 head
拼接链表

class ListNode{
  constructor(val,next){
    this.val = val;
    this.next = null;
  }
}

var reverseBetween = function(head, left, right){
  // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
  let dummyNode = new ListNode(-1,head)

  // 找到需要反转的位置
  let pre = dummyNode
  for(let i=1;i<left;i++){
    pre = pre.next
  }
  // 反转节点
  head = pre.next
  for(let i=left;i<right;i++){
    let next = head.next
    // next 节点要被放到反转部分的头部，所以将head的next指向它的下下个节点
    head.next = head.next.next
    // 将next放到头部，pre.next指向的是反转部分的头部节点
    next.next = pre.next
    // 重新将pre指向反转部分的头部
    pre.next = next
  }

  return dummyNode.next
};

console.log(reverseBetween(head,left,right))

const head = {
  'val':1,
  'next':{
    'val':2,
    'next':{
      'val':3,
      'next':{
        'val':4,
        'next':{
          'val':5,
          'next':undefined
        }
      }
    }
  }
}
const left = 2
const right = 4
console.log(reverseBetween(head,left,right))

92. 反转链表 II
代码