1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        int length = GetLengthListNode(head);
        if(length <= 0 || m >= n || length < n) return head;
        while(m < n) {
            head = reverseBetweenStep(head,m,n);
            m++;
            n--;
        }
        return head;
    }
private:
    ListNode *reverseBetweenStep(ListNode *head, int m, int n) {
        if(n-m == 1) {
            if(m == 1) {
                ListNode * mlistNode = head;
                ListNode * nlistNode = GetListNodeFromPos(head,n);
                ListNode * ntmpnext = nlistNode->next;
                nlistNode->next = mlistNode;
                mlistNode->next = ntmpnext;
                return nlistNode;
            }
            else {
                ListNode * beforem = GetListNodeFromPos(head,m-1); 
                ListNode * mlistNode = GetListNodeFromPos(head,m);
                ListNode * nlistNode = GetListNodeFromPos(head,n);
                ListNode * ntmpnext = nlistNode->next;
                nlistNode->next = mlistNode;
                mlistNode->next = ntmpnext;
                beforem->next = nlistNode;
                return head;<br />
            }
        }
        if(m == 1) {
            ListNode * mlistNode = head;
            ListNode * beforen = GetListNodeFromPos(head,n-1);
            ListNode * nlistNode = GetListNodeFromPos(head,n);
            ListNode * ntmpnext = nlistNode->next;
            nlistNode->next = mlistNode->next;
            mlistNode->next = ntmpnext;
            beforen->next = mlistNode;
            return nlistNode;
        }
        else {
            ListNode * beforem = GetListNodeFromPos(head,m-1); 
            ListNode * mlistNode = GetListNodeFromPos(head,m);
            ListNode * beforen = GetListNodeFromPos(head,n-1);
            ListNode * nlistNode = GetListNodeFromPos(head,n);

            ListNode * mtmpnext = mlistNode->next;
            ListNode * ntmpnext = nlistNode->next;
            nlistNode->next = mlistNode->next;
            mlistNode->next = ntmpnext;
            beforen->next = mlistNode;
            beforem->next = nlistNode;
            return head;            
        }
    }
};
ListNode * GetListNodeFromPos(ListNode *head,int pos) {
    pos--;
    while(pos--) {
        head = head->next;
    }
    return head;
}
int GetLengthListNode(ListNode *listNode) {
    int Length = 0;
    while(listNode != NULL) {
        listNode = listNode->next;
        Length++;
    }
    return Length;
};