LeetCode-92. Reverse Linked List II

发表于 分类于

问题描述

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

1
2
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

解答

需要注意的是，在表头之前额外增加了一个节点res，res的next指向表头，这样是为了更方便得处理从表头开始反转时的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * @Description: 反转链表内的指定区间
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
const reverseBetween = function (head, left, right) {
  let res = new ListNode()
  res.next = head
  let pre = res
  let cur = head

  for (let i = 1; i < left; i++) {
    pre = cur
    cur = cur.next
  }

  for (let j = left; j < right; j++) {
    let temp = cur.next
    cur.next = temp.next
    temp.next = pre.next
    pre.next = temp
  }
  return res.next
}