Reverse Linked List II

Reverse a linked list from position m to n.

Have you met this question in a real interview? 

Yes

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.

Challenge

Reverse it in-place and in one-pass

/**
 * Definition of singly-linked-list:
 * 
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The head of linked list.
     * @param m: The start position need to reverse.
     * @param n: The end position need to reverse.
     * @return: The new head of partial reversed linked list.
     */
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // write your code here
        ListNode dummy(0);
        dummy.next=head;
        head=&dummy;
        for (int i=1; i<m; i++){
            if(head)
                head=head->next;
            else
                return 0;
        }
        
        ListNode* prev=0;
        ListNode* cur = head->next;
        ListNode* next = cur;
        for(int i=m; i<=n; i++){
            next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        head->next->next=cur;
        head->next = prev;
        return dummy.next;
    }
};