Reverse Linked List II

ListNode *reverseBetween(ListNode *head, int m, int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    ListNode dummy(0);
    dummy.next = head;

    ListNode *preM, *pre = &dummy;
    for (int i = 1; i <= n; ++i) {
        if (i == m) preM = pre;

        if (i > m && i <= n) {
            pre->next = head->next;
            head->next = preM->next;
            preM->next = head;
            head = pre; // head has been moved, so pre becomes current
        }

        pre = head;
        head = head->next;
    }

    return dummy.next;
}

Way 1:
ListNode *reverseBetween(ListNode *head, int m, int n) {
    if (!head) return head;
    ListNode dummy(0);
    dummy.next = head;
    ListNode *preM, *prev = &dummy;
    for (int i = 1; i <= n; i++) {
        if (i <= m) {
            if (i == m) preM = prev;
            prev = head;
            head = head->next;
        } else { //m < i <=n
            prev->next = head->next;
            head->next = preM->next;
            preM->next = head;
            head = prev->next;
        }
    }
    return dummy.next;
}

Way 2:
ListNode *reverseBetween(ListNode *head, int m, int n) {
    if (!head) return head;

    ListNode dummy(0);
    dummy.next = head;
    ListNode *prev = &dummy;
    ListNode *curr = head;

    int i = 0;
    while (curr && ++i<n) {
        if (i<m) prev = curr;
        curr = curr->next;
    }
    curr = reverse(prev, curr->next);
    return dummy.next;
}
ListNode *reverse(ListNode *begin, ListNode *end)
{
    ListNode *last = begin->next;
    ListNode *curr = last->next;
    while (curr != end) {
        last->next = curr->next;
        curr->next = begin->next;
        begin->next = curr;
        curr = last->next;
    }
    return last;
}

ListNode *reverseBetween(ListNode *head, int m, int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int step = n-m;
    ListNode* safeG = new ListNode(-1); //intro a safe guard to avoid handle head case.
    safeG->next = head;
    head = safeG;

    ListNode* pre = head;
    while(m>1)
    {
        pre=pre->next;
        m--;
    }

    assert(pre);
    ListNode* cur = pre, *post = pre->next;

    if(step>=1)
    {
        while(step+1>0 && post!=NULL)
        {
            ListNode* temp = post->next;
            post->next = cur;
            cur = post;
            post = temp;
            step--;
        }

        ListNode* temp = pre->next;
        pre->next = cur;
        temp->next = post;
    }

    safeG = head;
    head = head->next;
    delete safeG;
    return head;        
}

    ListNode *reverseBetween(ListNode *head, int m, int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    ListNode *p,*pre;
    if (head==0 || head->next == 0 || n<=m) return head;

    for (pre=NULL,p=head;p!=NULL && m>1;)
    {
        pre = p;
        p=p->next;
        m--;
        n--;
    }

    // p points to node[m]

    //normal list reverse routing plus a coutner of n
    ListNode *q=p;
    p = NULL;
    while (q && n>0)
    {
        ListNode *ne=q->next;
        q->next = p;
        p=q;
        q=ne;
        n--;
    }
    // p points to header of reverses portion
    // q points to the first not reversed node after n
    if (pre)
    {
        pre->next->next = q;
        pre->next = p;
        return head;
    }
    else
    {
        head->next=q;
        return p;
    }            
}

public ListNode reverseBetween(ListNode head, int m, int n) {
    // Start typing your Java solution below
    // DO NOT write main() function
    if(m==n)
        return head;
    ListNode temp=head,beginner,tail,middle;
    int move=1;
    while(move<m-1){
        temp=temp.next;
        move++;
    }
    if(m==1){
        beginner=head;
        middle=beginner.next;
        tail=beginner.next.next;
    }else{
        beginner=temp.next;
        tail=beginner.next.next;
        middle=beginner.next;
    }
    while(m<n){
        middle.next=beginner;
        beginner=middle;
        middle=tail;
        if(tail!=null)
            tail=tail.next;
        m++;
    }
    if(head.next.next==head){
        head.next=middle;
        head=beginner;
        return head;
    }
    temp.next.next=middle;
    temp.next=beginner;
    return head;

}

public ListNode reverseBetween(ListNode head, int m, int n) {
    int index = 0;
    ListNode root = new ListNode(0);
    root.next = head;
    ListNode cur_node = root;
    ListNode pre_m_node = root, m_node = root;
    while (index < m) {
        index++;
        if (index == m) {
            pre_m_node = cur_node;
            m_node = cur_node.next;
        }
        cur_node = cur_node.next;
    }

    index++;
    cur_node = m_node.next;
    while (index <= n) {
        m_node.next = cur_node.next;
        cur_node.next = pre_m_node.next;
        pre_m_node.next = cur_node;
        cur_node = m_node.next;
        index++;
    }

    return root.next;
}

public class ReverseBetween {
public ListNode reverseBetween(ListNode head, int m, int n) {
    if (head==null) return null;
    if (m==1) {
        ListNode currn = head.next;
        ListNode end = head;
        ListNode nextn=null;
        while (n>1) {
            if (currn!=null) {
                nextn = currn.next;
                currn.next=head;
                head=currn;
                currn=nextn;
                n--;
            } else
                break;
        }
        end.next=currn;
        return head;
    }
    else {
        ListNode newhead = reverseBetween2(head.next,m-1,n-1);
        if (newhead != head.next) {
            head.next=newhead;
        }
        return head;
    }
}
}

/*
    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.
    */

    #include <iostream>
    #include <string>
    #include <utility>

    using namespace std;

    struct node{
        int val;
        node* next;
        node(int v):val(v),next(NULL){};
    };

    struct Solution{
        node* root;
        int length;
        Solution():root(NULL), length(0){}; //must initialize
        node* make_list(int *e, int m){
            node* previous = NULL;
            length = m;
            if (m == 0 || e == NULL) return NULL;
            for (int i = 0; i < m; ++i){
                node* n = new node(e[i]);
                if (previous != NULL) previous->next = n;
                if (root == NULL) root = n;
                previous = n;
            }
            return root;
        }

        node* ReverseLinkedListII(int m, int n){
            if (m < 1 || n < 1 || m > length || n > length || m >= n) return NULL;  
            node *left = root, *previous, *current;
            if (m == 1){
                left = NULL;
                previous = root;
                current = root->next;
            }
            else{
                int i = m;
                while (--i > 1){
                    left = left->next; //m - 1;
                }
                previous = left->next; //m
                current  = previous->next;  //m + 1
            }
            while (m < n){
                node* nextnext = current->next; //m + 2
                current->next  = previous;
                previous = current; //m + 1
                current  = nextnext; // m + 2
                ++m;
            }
            (NULL == left) ? (root->next = current) : (left->next->next = current); //m -> n + 1 
            (NULL == left) ? (root = previous) : (left->next = previous); //m - 1 -> n     
        }

        node* print(){
            node* n = root;
            do{
                cout << n->val << "->";
                n = n->next;
            }while (NULL != n);
            cout << "NULL" << endl;
        }
    };

    int main(){
        int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        Solution sol;
        sol.make_list(a, 9);
        sol.ReverseLinkedListII(2, 9);
        sol.print();
        sol.ReverseLinkedListII(1, 4);
        sol.print();
        sol.ReverseLinkedListII(1, 5);
        sol.print();
        return 0;
    }

ListNode *reverseList(ListNode *p, int m, int n, int current,
    ListNode **mp0, ListNode **mp, ListNode **np, ListNode **np1) {
    if (m-1 < 1) {
        *mp0 = NULL;
    } else if (current == m-1) {
        *mp0 = p;
    }
    if (current == m) {
        *mp = p;
    }
    if (current == n) {
        *np1 = p->next;
        *np = p;
        return p;
    }

    ListNode *nx = reverseList(p->next, m, n, current+1, mp0, mp, np, np1);
    if (current >= m && current < n) {
        nx->next = p;
    }

    return p;
}

ListNode *reverseBetween(ListNode *head, int m, int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    ListNode *mp0, *mp, *np, *np1;
    reverseList(head, m, n, 1, &mp0, &mp, &np, &np1);

    if (mp0 == NULL) {
        head = np;
    } else {
        mp0->next = np;
    }
    mp->next = np1;
    return head;
}

public ListNode reverseBetween(ListNode head, int m, int n) {
    if(head==null||m==n)
        return head;

    ListNode prev=head,cur=head;

    if(m==1){
        prev = new ListNode(-1);            
        prev.next = head;            
    }

    int count = 0;        
    while(cur.next!=null&&count<n-1){
        count++;
        while(count<m){
            count++;
            prev = cur;
            cur=cur.next;
        }
        ListNode temp = prev.next;
        prev.next=cur.next;
        cur.next=cur.next.next;
        prev.next.next=temp;

    }
    if(m==1)
        return prev.next;        
    return head;
}