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) {
ListNode dummy(0, head);
ListNode *prev_left_node = &dummy;
for (int i = 1; i < left; ++i) {
prev_left_node = prev_left_node->next;
}
ListNode *left_node = prev_left_node->next;
ListNode *prev = prev_left_node;
ListNode *curr = left_node;
for (int i = left; i <= right; ++i) {
ListNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
prev_left_node->next = prev;
left_node->next = curr;
return dummy.next;
}
};