反转链表II-92

[sl1673495]

92.反转链表 II 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

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

示例:

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

思路

这题相对于反转链表的第一题，就比较有难度了，所以说它是 medium 难度。

需要考虑的点很多：

1. 首先需要找出需要反转的链表的起点 node，终点 node。

2. 并且还需要记录下来需要反转的起点的前一个点 sliceStartPrev。

3. 需要反转的终点的后一个节点 sliceEndNext。

4. 在反转完成后要把起点的前一个节点的 sliceStartPrev 的 next 设为反转链表后的 head 头部。

5. 并且把反转后链表的 tail 尾部的 next 设置成 sliceEndNext。

当然，反转链表的部分还是可以沿用第一题的代码啦。

/**
 * 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}
 */

let reverseBetween = function (head, m, n) {
  let i = 1
  let sliceStartPrev = null
  let sliceStart = null
  let sliceEnd = null
  let cur = head

  // 记录切分起点的前一个节点，和切分终点的后一个节点
  while (i <= n) {
    if (i === m - 1) {
      sliceStartPrev = cur
    }
    if (i === m) {
      sliceStart = cur
    }
    if (i === n) {
      sliceEnd = cur
    }
    cur = cur.next
    i++
  }

  let sliceEndNext = sliceEnd.next
  // 切断切分终点的next 防止反转的时候反转过头
  sliceEnd.next = null

  const { head: slicedHead, tail: slicedTail } = reverse(sliceStart)
  if (sliceStartPrev) {
    // 如果需要反转的部分有前一个节点 那么只需要在中间动手脚 原样返回head节点即可
    sliceStartPrev.next = slicedHead
  } else {
    // 这里需要注意的是 如果没有sliceStartPrev 说明是从第一个节点就开始反转的
    // 那么我们需要手动调整head为反转后的head
    head = slicedHead
  }
  slicedTail.next = sliceEndNext

  return head
}

function reverse(head) {
  let prev = null
  let cur = head
  while (cur) {
    let next = cur.next
    cur.next = prev

    prev = cur
    cur = next
  }
  // 返回反转后的头尾节点
  return { head: prev, tail: head }
}

[MJingv]

难懂