Description
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Examples
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
Answer
Do it in one-pass means that this problem only allows iteration method. The idea is the same as Reverse Linked List. The only difference is in this problem we need to set the start point and the end point of the reverse part using loop.
Time Complexity
O(n) as n equals to n given in input.
Code
C++
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(!head || !head->next) return head;
ListNode* start = head;
ListNode* pre = new ListNode(0);
pre->next = head;
for(int i = 1; i < m; ++i)
{
start = start->next;
pre = pre->next;
}
int count = m;
while(start && start->next && count < n)
{
ListNode* temp = pre->next;
pre->next = start->next;
start->next = start->next->next;
pre->next->next = temp;
count++;
}
if(m != 1) return head;
return pre->next;
}
};
