Leetcode/offer24reverse_List.cpp at main · yayajjiang/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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
      //4. iteration
        ListNode* prev = nullptr;//needs to initialize first
        while(head!=nullptr){
            ListNode *temp = head->next;
            head->next = prev;
            prev=head;
            head=temp;
        }
        return prev;


        //1. change the value for each node, reverse order
        //needs to comfirm with hr, change the oringinal link or not

        // vector<int> v;
        // ListNode* copy = head;
        // ListNode* ans = head;

        // while(head!=nullptr){
        //     v.push_back(head->val);
        //     head = head->next;
        // }
        // for(int i = 0; i<v.size(); i++){
        //     copy->val = v[v.size()-i-1];
        //     copy = copy->next;
        // }
        // return ans;

        //2. change the pointers
        //FILO, use stack to reverse
//         stack<ListNode*> s;
//         if(head == nullptr){
//             return head;
//         }

//         while(head!=nullptr){
//             s.push(head);
//             head = head->next;
//         }
//         ListNode* ans;
//         //654321
//         //ans 65
//         //copy (save the head pointer)
//         // dummyhead = s.top();
//         ans =  s.top();
//         ListNode* copy = ans;
//         s.pop();
//         while(!s.empty()){
//             ans->next = s.top();
//             s.pop();
//             ans = ans->next;
//             //ans->next = nullptr;    //1-2, 1-null
//         }
//         ans->next = nullptr;
//         return copy;


      //3.use vector to store the nodes
        vector<ListNode*> v;
        ListNode* copy = head;
        if(head == nullptr){
            return head;
        }
        ListNode* dummy = new ListNode(-1);//needs to delete it after use
        ListNode* laji = dummy;
        //ListNode* a = dummy;
        ListNode* ans;
        while(copy!=nullptr){
            v.push_back(copy);
            copy = copy->next;
        }
        //cout<<v.at(4)->val;
        int i = 0;
        while(!v.empty()){

            laji->next = v.back();
            //cout<<v.back()->val;
            if(i == 0){
                ans = laji->next;
                //cout<<ans->val;
            }
            v.pop_back();
            laji = laji->next;
            laji->next = nullptr;//IMPORTANT needs to break the link
            i++;

        }
        //laji->next = nullptr;//IMPORTANT needs to break the link
        // delete dummy;
        // dummy = nullptr;
        // cout << laji->val;
        //delete laji;
        return ans;
    }
};