92. Reverse Linked List II
1. Description
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.
2. Example
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]
3. Constraints
- The number of nodes in the list is n.
- 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n
4. Solutions
Two Pointers
Time complexity: O(right)
Space complexity: O(1)
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int left, int right) {
if (left == right) {
return head;
}
ListNode dummy(0, head);
ListNode *prev_left = &dummy;
int index = 1;
while (index < left) {
++index;
prev_left = prev_left->next;
}
ListNode *left_node = prev_left->next;
ListNode *prev = nullptr, *current = left_node, *next = nullptr;
while (index <= right) {
++index;
next = current->next;
current->next = prev;
prev = current;
current = next;
}
prev_left->next = prev;
left_node->next = current;
return dummy.next;
}
};