Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
翻转完毕之后，记得处理下头尾即可
代码：
class Solution { public: ListNode *reverseBetween(ListNode *head, int m, int n) { if(head==NULL) return head; //加一个哨兵 ListNode* headTag=new ListNode(0); headTag->next=head; ListNode* prep=headTag; ListNode* p=headTag; ListNode* q=headTag; int prepStep2=m-1; int qSteps=n-m; while (prepStep2>0) { prep=prep->next; --prepStep2; } p=prep->next; q=p->next; ListNode* temp; ListNode* tempFirst=p; bool firstTag=true; while (qSteps) { temp=q->next; q->next=p; if(firstTag) {p->next=NULL;firstTag=false;} p=q; q=temp; --qSteps; } prep->next=p; tempFirst->next=q; return headTag->next; } };
原文：http://www.cnblogs.com/fightformylife/p/4242432.html