学步园

Reverse Linked
List II:

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.

最近写代码的时候老忘记在while循环里对变量做 减减或者加加。。。然后就死循环了。。

#define LN ListNode
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
            if ( m==n )
                return head;
        	n=n-m+1;
			m--;
			LN guard(-1);
			guard.next=head;
			LN* tail1=&guard;
			LN* cur=head;
			while(m&&cur)
			{
					tail1=tail1->next;
					cur=cur->next;
					m--;
			}
			assert(cur);
			LN* tail2=cur;
			tail1->next=NULL;
			while(cur&&n)
			{
					LN* tmp=cur->next;
					cur->next=tail1->next;
					tail1->next=cur;
					cur=tmp;
					n--;
			}
			assert(n==0);
			tail2->next=cur;
			return guard.next;
	}
};