[剑指offer][03]从尾到头打印链表

题目描述：

· 输入一个链表，从尾到头打印链表每个节点的值。

解题思路：

思路1：

第一反应是将链表中的指针反转，改变链表的方向，然后再从头打印出来（该方法改变了原来链表的结构，这就要看面试或笔试时的要求，可否改变链表结构）

思路2：

遍历链表时是从头到尾，而打印链表时却是从尾到头，典型的“先进后出”——栈的特点，从而可以用栈来实现。每遍历一个节点，把该节点放到一个栈中，当遍历完整个链表后，再从栈顶开始逐个输出节点的值，此时输出的节点顺序已经反转过来了。

思路3：

栈可以实现，而递归本质上也是一个栈结构，从而可以用递归来实现。即：没遍历到一个节点时，先递归输出其后面的一个节点的值，再输出该节点本身的值。

代码实现

思路1：

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *pNext, *pTemp;
        vector<int> res;
        //边界检查
        if (head == nullptr)
            return res;
        //处理头指针
        pNext = head->next;
        pTemp = head;
        head->next = nullptr;
        //单链表逆序
        while (pNext != nullptr){
            pTemp = pNext;
            pNext = pNext->next;
            pTemp->next = head;
            head = pTemp;
        }
        //逆序打印
        while (head != nullptr){
            res.push_back(head->val);
            head = head->next;
        }
        return res;
    }
};

思路2：

思路3：

参考链接

面试题8：从尾到头打印单链表