Reverse Linked List II. Reverse a linked list from position m to n. Do it in-place and in one-pass. Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

reverse_linked_listII.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
     ListNode * newHead = NULL;
     ListNode * newTail = NULL;
     ListNode * tail = head, *PrevOfNewList = NULL;
     // scan to the end, reverse M to N 
     //   inserting newEle in front of newHead, update newHead
     //   newTail-> tail'sNext
     
     //Note: if m == 1, then must return newHead
     //     else, return oldHead (reversed LL as a section inside)
     int nodeCnt = 0;
     while(tail) {
         nodeCnt ++;
         if (nodeCnt == m-1)
            PrevOfNewList = tail;
         if (nodeCnt < m ) {
             tail = tail->next;
             continue;
         }
         if (nodeCnt > n)
            break;
            
         //now reverse the list
         ListNode *tailNext = tail->next;            
         if (!newHead) {
             newHead = tail;                   
             newTail = newHead;         
         }
         else { //     tail --> newHead, then update newHead
             tail->next = newHead;      
             newHead = tail;         
         }
         newTail->next = tailNext;    
         
         tail = tailNext;         
         
     }
     if (PrevOfNewList)
        PrevOfNewList->next = newHead;
     if (m == 1)
        return newHead;
    return head;
    }
};