从尾到头打印链表

1.调用库函数reverse实现vector内部元素的翻转.2.递归法3.堆栈法4.反转链表(改变链表结构)5.利用vector的insert特性
原题：
https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=23278&ru=/practice/75e878df47f24fdc9dc3e400ec6058ca&qru=/ta/coding-interviews/question-ranking

时间:o(n) 空间:o(n)

class Solution {
public:
    vector printListFromTailToHead(ListNode* head) {
        vector A;
        while(head){ // while(head!=NULL)  while(head!=nullptr) 也可。
            A.push_back(head->val);
            head = head->next;
        }
        reverse(A.begin(), A.end()); // 直接调用库函数实现vector内部元素的翻转.
        return A;
    }
};

时间:o(n) 空间:o(n)
但这种方法会出现堆栈溢出（递归调用层数太多）。即链表非常长时可能导致函数调用栈溢出。

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

时间:o(n) 空间:o(n)

class Solution {
public:
    vector printListFromTailToHead(ListNode* head) {
        vector res;
        stack nodes;
        ListNode* node = head;
        // 入栈
        while(node != nullptr){ // 或 head != NULL 或 while(head)
            nodes.push(node->val);
            node = node->next;
        } 
        // 出栈 并将出栈节点存入res
        while(!nodes.empty()){
            res.push_back(nodes.top());
            nodes.pop();
        }
        return res;
    }
};

简化一下：

class Solution {
public:
    vector printListFromTailToHead(ListNode* head) {
        vector res;
        stack nodes;
        // 入栈
        while(head != nullptr){  // 或 head != NULL 或 while(head)
            nodes.push(head->val);
            head = head->next;
        } 
        // 出栈 并将出栈节点存入res
        while(!nodes.empty()){
            res.push_back(nodes.top());
            nodes.pop();
        }
        return res;
    }
};

时间复杂度：O(n), 遍历一次链表
空间复杂度：O(1)

class Solution {
public:
    vector printListFromTailToHead(ListNode* head) {
        ListNode *pre = nullptr;
        ListNode *cur = head;
        ListNode *nex = head; // ListNode *nex = nullptr;也ok。
        // 通过移动3个指针反转链表（生成了一个新的链表，是原链表的反转链表）
        while(cur){ // 循环条件是 原链表的当前结点不为空指针
            // 第一步：保存当前结点的下一个节点
            nex = cur->next;
            // 第二步：令原链表的当前节点的next指针指向反转链表的最后一个节点(就是pre指向的结点，记住pre初始是空指针)，
            //        也代表切断了原链表的当前结点和其下一个节点的联系。
            cur->next = pre;
            // 第三步：(令)反转链表的最后一个结点即原链表的当前结点。
            pre = cur; 
            // 第四步：(令)原链表的当前结点指向原链表的下个结点。至此，一轮循环结束。如此重复。
            cur = nex;
        }
        // while循环结束后，cur当然为nullptr，pre指向反转链表的头节点。
        
        vector res;
        while(pre){
            res.push_back(pre->val);
            pre = pre->next;
        }
        return res;       
    }
};

class Solution {
public:
    vector reversePrint(ListNode* head) {
        vector res;
        ListNode* pre=head;
        while(pre){
            res.insert(res.begin(),pre->val);
            pre=pre->next;
        }
        return res;
    }
};

class Solution {
public:
    vector printListFromTailToHead(ListNode* head) {
        vector res;
        if(!head) return res;
        while(head){
        	// 每一轮在头部插入
            res.insert(res.begin(), head->val);
            head = head->next;
        }
        return res;       
    }
};