剑指Offer - 面试题6. 从尾到头打印链表（栈，递归，反转链表）

示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
 
限制：
0 <= 链表长度 <= 10000

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        stack<int> s;
        while(head)
        {
        	s.push(head->val);
        	head = head->next;
        }
        vector<int> ans;
        while(!s.empty())
        {
        	ans.push_back(s.top());
        	s.pop();
        }
        return ans;
    }
};

class Solution {
	vector<int> ans;
public:
    vector<int> reversePrint(ListNode* head) {
        dfs(head);
        return ans;
    }

    void dfs(ListNode* head)
    {
    	if(!head)
    		return;
    	dfs(head->next);
    	ans.push_back(head->val);
    }
};

class Solution {
	vector<int> ans;
public:
    vector<int> reversePrint(ListNode* head) {
    	if(!head)
    		return {};
        head = reverseList(head);
        while(head)
        {
        	ans.push_back(head->val);
        	head = head->next;
        }
        return ans;
    }

	ListNode* reverseList(ListNode* head)
	{	//反转链表，返回新表头
		ListNode *prev = NULL, *nt = head->next;
		while(head && head->next)
		{
			head->next = prev;
			prev = head;
			head = nt;
			nt = nt->next;
		}
		head->next = prev;
		return head;
	}    
};