【剑指offer】从尾到头打印链表--C++实现

一：由于题目要求返回一个vector，首先想到的是直接使用vector的方法来做，即遍历链表，每经过一个链表就将一个值插入vector的开头位置。

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> arrayList;
        if (head!=NULL)
        {
            arrayList.push_back(head->val);
            while (head->next != NULL)
            {
                arrayList.insert(arrayList.begin(), head->next->val);
                head = head->next;
            }
        }
        return arrayList;
    }

};

代码里使用的是vector的insert方法从而在vector的开头插入元素，故每次插入元素时都要移动插入点后续的所有元素（在记vector的长度为n的情况下，本题里需要移动的次数是n²级的），开销相对第二种方法来说较大。

二：由于题目是从尾到头打印链表，而题目给出的是一个单链表，只能从头往后遍历，即需要“先进后出”，于是使用栈结构：

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        vector<int> arrayList;
        stack<int> arrayStack;
        while (head != NULL)
        {
            arrayStack.push(head->val);
            head = head->next;
        }
        while (!arrayStack.empty())
        {
            // 若不是题目要求返回vector<int> 那么可以直接将整个栈返回，打印栈。
            // 也可以直接在函数里打印，而不需要返回值
            arrayList.push_back(arrayStack.top());
            arrayStack.pop();
        }
        return arrayList;
    }
};

转移元素时使用的是push_back，直接在尾部插入，不需移动元素，虽然多了个循环，但在运算次数上明显比第一种方法少，并且转移元素这一步骤非必须。