leetcode/reverse-linked-list.cpp at master · almaleksia/leetcode · GitHub

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
76
77
78
79
80
/**
 * 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) {
        if ( m == n ) return head;

        int i = 1;
        int head_begin = 0;
        ListNode* subhead = head;
        ListNode* cur = NULL;
        stack<ListNode*> st;

        ListNode* save_subhead = subhead;
        while( i <= n ) {

            if ( i < m && subhead->next != NULL) {
                save_subhead = subhead;
                subhead = subhead->next;
            }

            if ( i >= m ) {
                if ( i == m ) {
                    if ( subhead == head ) {
                        head_begin = 1;
                        cur = subhead;
                    } else {
                        cur = save_subhead->next;
                        subhead = save_subhead;
                    }
                }
                else {
                    if ( cur->next != NULL ) {
                        cur = cur->next;
                    } else { break; }
                }

                st.push(cur);
            }

            i++;
        }

        ListNode* tail = NULL;
        int first = 1;

        while( !st.empty() ) {
            if ( first ) {
                tail = st.top();
                tail = tail->next;
                first = 0;

                if ( head_begin) {
                    head = subhead = st.top();
                } else {
                    subhead->next = st.top();
                }

                cur = st.top();
            } else {
                cur->next = st.top();
                cur = cur->next;
            }

            st.pop();
        }

        if ( cur != NULL ) {
            cur->next = tail;
        }

        return head;
    }
};