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. Follow Up
- Could you do it in one pass?
5. Solutions
My Accepted Solution(Follow Up)
n is the number of nodes in m_head
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int left, int right) {
if (left == right) {
return head;
}
ListNode *guard_head = new ListNode();
guard_head->next = head;
ListNode *list1 = guard_head;
for (int i = 1; i < left; ++i) {
list1 = list1->next;
}
ListNode *sub_tail = list1->next;
ListNode *head_prev = sub_tail;
ListNode *sub_head = sub_tail->next;
for (int i = 1; i < right - left; ++i) {
ListNode *head_next = sub_head->next;
sub_head->next = head_prev;
head_prev = sub_head;
sub_head = head_next;
}
sub_tail->next = sub_head->next;
sub_head->next = head_prev;
list1->next = sub_head;
return guard_head->next;
}
};