struct ListNode 
{
    int val;
    ListNode *next;
    ListNode(int x = 0) : val(x), next(NULL) {}
};

ListNode *ReverseBetween(ListNode *head, int m, int n) 
{
	//if (m == n) return head;

	ListNode** h = &head; //the start of list for reversing
	n = n-m+1; //how many nodes need to be reversed
    while(--m > 0)h = &((*h)->next);

    //reverse the nodes in [m,n]
    ListNode* cur = *h;
    ListNode* pre = NULL;
    ListNode* nxt;
    while(n-- > 0)
    {
    	nxt = cur->next;
    	cur->next = pre;

    	pre = cur;
    	cur = nxt;
    }

    //make the original fisrt node point to next node of original last
    (*h)->next = cur;
    //make head point to original last node
    *h = pre;

    return head;
}