Leetcode 92 - Reverse linked list II

Note:

  • Not like normal reversing linked list, we need to fix a prev pointer and only move curr.
  • Use a dummy in case left is equal to 1.
  • img
  • The most important step: tmp.next = prev.next. Don’t use tmp.next = curr.

Question:

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:

img

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

Code:

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
/**
* 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}
*/
var reverseBetween = function(head, left, right) {
let dummy = new ListNode();
dummy.next = head;
let prev = dummy;
let i = 1;
while (i < left) {
i++;
prev = prev.next;
}
let curr = prev.next;
while (i < right) {
i++;
let tmp = curr.next;
curr.next = tmp.next;
tmp.next = prev.next;
prev.next = tmp;
}
return dummy.next;
};