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.

reverseBetween.cc

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode *reverseList(ListNode *head, ListNode *end)
    {
        if(end == head->next)
        {
            return head;
        }
        else
        {
            ListNode * newHead = reverseList(head->next, end);
            head->next->next = head;
            head->next = NULL;
            return newHead;
        }
    }
    
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        // find m-1 node and n+1 node
        if(m == n)
            return head;
        
        ListNode guard(-1);
        guard.next = head;
        ListNode * pre = &guard;
        for(int i = 0; i<m-1; ++i)
            pre = pre->next;
        ListNode * aft = pre;
        for(int i = 0; i<n-m+2; ++i)
            aft = aft->next;
            
        // reverse list in [m,n]
        ListNode * newSubHead = reverseList(pre->next, aft);
        pre->next->next = aft;
        pre->next = newSubHead;
        
        if(pre == &guard) // head
        {
            return newSubHead;
        }else
            return head;
    }
};