We will iterate to the node before the start of the reversion. Then reverse.At the time of reverse, curr -> next will point to the tail of reversed inner linked list.
After reverse, we have three linked list, the first part, the reversed part, and the third part.
We want to point the tail of first part to the head of reversed part, which is pointed by prev. We also need to point the tail of reversed part, which is pointed by curr -> next, to head of third part, which is pointed by tempCurr.
tempCurr will point to the node after reversed inner linked list.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head == NULL)
return head;
//go ahead m - 1 step and reverse (n - m + 1 times )
//then point prev
ListNode dummyNode(-1);
dummyNode.next = head;
ListNode* curr = &dummyNode;
for(int i = 0; i < m - 1; i ++){
curr = curr -> next;
}
//curr will be right before the to-be-reversed node
ListNode* tempNext = NULL;
ListNode* prev = NULL;
ListNode* tempCurr = curr -> next;
for(int i = m - 1; i < n; i ++){
tempNext = tempCurr -> next;
tempCurr -> next = prev;
prev = tempCurr;
tempCurr = tempNext;
}
//after reversing n - m + 1 nodes, prev will be on the next node
//need to point tail of reverse(pointed by curr -> next) to tempCurr.
//need to point curr to head of reversed(pointed by prev) to tempCurr
curr -> next -> next = tempCurr;
curr -> next = prev;
return dummyNode.next;
}
};