学步园

题目描述如下:

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.

可以看出编号是从1开始的，最讨厌这种不是从0开始的了，处理跑的长度的时候超恶心啊；

 #define ln ListNode
class Solution {
public:
ln* reverseBetween(ln* head,int m,int n)
{
    if ( !head || !head->next || m<1 )
		return head;
    n=n-m+1;
	ln* guard=new ln(-1);
	guard->next=head;
	ln* pPre=guard;
	while(pPre&&--m)
	{
		pPre=pPre->next;
	}
	//not enough m nodes;
	if ( pPre==NULL)
	{
		delete guard;
		return head;
	}
	ln* pAfter=pPre->next;
	while(pAfter&&n--)
	{
		pAfter=pAfter->next;
	}

	_reverseList(pPre,pAfter);
	ln* ans=guard->next;
	delete guard;
	return ans;
}
void _reverseList(ln*& pPre,ln* pAfter)
{
	ln* pCur=pPre->next;
	pPre->next=pAfter;
	while(pCur!=pAfter)
	{
		ln* tmp=pCur->next;
		pCur->next=pPre->next;
		pPre->next=pCur;
		pCur=tmp;
	}
}
};