Reverse Linked List II

class Solution:
    # @param head, a ListNode
    # @param m, an integer
    # @param n, an integer
    # @return a ListNode
    def reverseBetween(self, head, m, n):
        dummyNode = ListNode(0)
        p = dummyNode
        q = head

        for x in range(m - 1):
            p.next = q
            q = q.next
            p = p.next

        start = None
        end = q
        next = None
        for x in range(m, n + 1):
            next = q.next
            q.next = start
            start = q
            q = next

        p.next = start
        end.next = next
        return dummyNode.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {  
    // Divide the list to three parts:   
    // 1)Nodes before m keep still;   
    // 2)Traverse m~n nodes;  
    // 3)Nodes after n keep still.  
    public ListNode reverseBetween(ListNode head, int m, int n) {  
        if (m == n) return head;  
          
        ListNode preHead = new ListNode(0);  
        preHead.next = head;  
          
        // The (m-1) node is the tail of first tail.  
        ListNode firstTail = preHead;  
        int k = m - 1;  
        while (k-- > 0) {  
            firstTail = firstTail.next;  
        }  
          
        // The m-th node is the traversed tail.  
        ListNode secondTail = firstTail.next;  
          
        // Traverse m~n nodes, and get the traversed head.  
        ListNode tmpHead = null;  
        ListNode tmpNext = null;  
        ListNode node = firstTail.next;  
        k = n - m + 1;  
        while (k-- > 0) {  
            tmpHead = node;  
            node = node.next;  
              
            tmpHead.next = tmpNext;  
            tmpNext = tmpHead;  
        }  
          
        // Connect three parts.  
        firstTail.next = tmpHead;  
        secondTail.next = node;  
          
        return preHead.next;  
    }  
}

/**
 * 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 *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = dummy;
        ListNode *pre, *front, *last;
        for (int i = 1; i <= m - 1; ++i) cur = cur->next;
        pre = cur;
        last = cur->next;
        for (int i = m; i <= n; ++i) {
            cur = pre->next;
            pre->next = cur->next;
            cur->next = front;
            front = cur;
        }
        cur = pre->next;
        pre->next = front;
        last->next = cur;
        return dummy->next;
    }
};