Print linked list from end to end

The original title is ：
https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=23278&ru=/practice/75e878df47f24fdc9dc3e400ec6058ca&qru=/ta/coding-interviews/question-ranking

1. Call library function reverse Realization vector Flip of internal elements .

Time :o(n) Space :o(n)

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */
class Solution {
    
public:
    vector<int> printListFromTailToHead(ListNode* head) {
    
        vector<int> A;
        while(head){
     // while(head!=NULL) while(head!=nullptr)  Can also be .
            A.push_back(head->val);
            head = head->next;
        }
        reverse(A.begin(), A.end()); //  Directly call library functions to realize vector Flip of internal elements .
        return A;
    }
};

2. Recursive method

Time :o(n) Space :o(n)
But this method will cause stack overflow （ Too many recursive call layers ）. That is, when the linked list is very long, it may cause function call stack overflow .

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */
class Solution {
    
public:
    vector<int> ans;
    vector<int> printListFromTailToHead(ListNode* head) {
    
        if(!head) return ans; // if(head == nullptr)  or  if(head == NULL)
        printListFromTailToHead(head->next);
        ans.push_back(head->val);
        return ans;        
    }
};

3. Stack method

Time :o(n) Space :o(n)

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */
class Solution {
    
public:
    vector<int> printListFromTailToHead(ListNode* head) {
    
        vector<int> res;
        stack<int> nodes;
        ListNode* node = head;
        //  Push 
        while(node != nullptr){
     //  or  head != NULL  or  while(head)
            nodes.push(node->val);
            node = node->next;
        } 
        //  Out of the stack   And store the outbound node in res
        while(!nodes.empty()){
    
            res.push_back(nodes.top());
            nodes.pop();
        }
        return res;
    }
};

To simplify the ：

class Solution {
    
public:
    vector<int> printListFromTailToHead(ListNode* head) {
    
        vector<int> res;
        stack<int> nodes;
        //  Push 
        while(head != nullptr){
      //  or  head != NULL  or  while(head)
            nodes.push(head->val);
            head = head->next;
        } 
        //  Out of the stack   And store the outbound node in res
        while(!nodes.empty()){
    
            res.push_back(nodes.top());
            nodes.pop();
        }
        return res;
    }
};

4. Reverse a linked list ( Change the list structure )

Time complexity ：O(n), Traverse the list once
Spatial complexity ：O(1)

class Solution {
    
public:
    vector<int> printListFromTailToHead(ListNode* head) {
    
        ListNode *pre = nullptr;
        ListNode *cur = head;
        ListNode *nex = head; // ListNode *nex = nullptr; also ok.
        //  By moving 3 Pointer reverse linked list （ Generated a new linked list , It is the reverse linked list of the original linked list ）
        while(cur){
     //  The cycle condition is   The current node of the original linked list is not a null pointer 
            //  First step ： Save the next node of the current node 
            nex = cur->next;
            //  The second step ： Make the current node of the original linked list next The pointer points to the last node of the inverted linked list ( Namely pre Pointed node , remember pre Initially null pointer ),
            //  It also means cutting off the connection between the current node of the original linked list and its next node .
            cur->next = pre;
            //  The third step ：( Make ) Reverse the last node of the linked list, that is, the current node of the original linked list .
            pre = cur; 
            //  Step four ：( Make ) The current node of the original linked list points to the next node of the original linked list . thus , The end of a cycle . repeat .
            cur = nex;
        }
        // while At the end of the cycle ,cur Of course nullptr,pre Point to the head node of the inverted linked list .
        
        vector<int> res;
        while(pre){
    
            res.push_back(pre->val);
            pre = pre->next;
        }
        return res;       
    }
};

5. utilize vector Of insert characteristic

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    vector<int> reversePrint(ListNode* head) {
    
        vector<int> res;
        ListNode* pre=head;
        while(pre){
    
            res.insert(res.begin(),pre->val);
            pre=pre->next;
        }
        return res;
    }
};

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */
class Solution {
    
public:
    vector<int> printListFromTailToHead(ListNode* head) {
    
        vector<int> res;
        if(!head) return res;
        while(head){
    
        	//  Insert each round in the head 
            res.insert(res.begin(), head->val);
            head = head->next;
        }
        return res;       
    }
};