92. Reverse Linked List II
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:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]
Constraints:
- The number of nodes in the list is
n
. 1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
Follow up: Could you do it in one pass?
题目大意
给定 2 个链表中结点的位置 m, n,反转这个两个位置区间内的所有结点。
解题思路
- 由于有可能整个链表都被反转,所以构造一个新的头结点指向当前的头;
- 找到第一个需要反转的结点的前一个结点 p,从这个结点开始,依次把后面的结点用“头插”法,插入到 p 结点的前面;
- 循环次数用 n-m 来控制。
代码
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function (head, left, right) {
if (!head || left === right) return head;
let res = new ListNode(0, head);
let prev = res;
// 移动prev指针,直至指向left - 1
for (let i = 0; i < left - 1; i++) {
prev = prev.next;
}
let cur = prev.next;
// 不断地将 cur.next 插入到 prev.next
for (let i = 0; i < right - left; i++) {
let temp = cur.next;
cur.next = temp.next;
temp.next = prev.next;
prev.next = temp;
}
return res.next;
};