剑指offer——从尾到头打印链表

题目链接: 从尾到头打印链表

题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
提示
以下方法都是针对不带头结点，如有问题，欢迎指正。

思路1

我们知道栈是有后进先出特性的，所以遍历链表，将链表元素值入栈，然后将栈中元素弹出到目标ArrayList;

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

思路2

我们可以利用递归的思想来遍历，借鉴之后的二叉树递归遍历

	class Solution {
	public:
	    vector<int> printListFromTailToHead(ListNode* head) {
	        vector <int> result;
	        if(head==nullptr){
	            return result;
	        }
	        result = printListFromTailToHead(head->next);
	        result.push_back(head->val)
	        return result;
	    }
	};

思路3

我们直接将链表用头插法逆置，然后遍历

	class Solution {
	public:
	    vector<int> printListFromTailToHead(ListNode* head) {
	        vector<int> result;
	        ListNode* p = head;
	        head = nullptr;
	        while(p!=nullptr){
	            ListNode* tmp = p->next;
	            p->next = head;
	            head = p;
	            p = tmp;
	        }
	        while(head!=nullptr){
	            result.push_back(head->val);
	            head = head->next;
	        }
	        return result;
	    }
	};

思路4

与思路3不同之处在于链表逆置的方法不不同，通过双指针来逆置

	class Solution {
	public:
	    vector<int> printListFromTailToHead(ListNode* head) {
	        ListNode* pre = nullptr;
	        ListNode* cur = head;
	        ListNode* tmp = head;
	        while(cur!=nullptr){
	            tmp = cur->next;
	            cur->next = pre;
	            pre = cur;
	            cur = tmp;
	        }
	        vector<int> result;
	        while(pre != nullptr){
	            result.push_back(pre->val);
	            pre = pre->next;
	        }
	        return result;
	    }
	};