key point no special data structure,
only operation trick listed as below.create a new node as a vritual head which will convinient
for the operation.change te node one bye one from m to n.
/**
* 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) {
//check the input
if (head == nullptr) return nullptr;
if (head - >next == nullptr) return head;
ListNode * headnode = new ListNode(0);
headnode - >next = head;
int i = 1;
ListNode * first = headnode;
ListNode * next = headnode;
ListNode * cur = headnode;
while (i < m) { //next node should be reversed that is m
first = first - >next;
i++;
}
ListNode * temp = first - >next;
next = first - >next - >next;
i += 1;
while (i <= n) {
if (next == nullptr) break;
cur = next;
next = next - >next;
cur - >next = first - >next;
first - >next = cur;
i++;
}
temp - >next = next;
head = headnode - >next;
delete headnode;
return head;
}
};
来源: http://www.bubuko.com/infodetail-2468355.html