tags:

• 链表
• 链表遍历
• vector

题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M

题目链接：剑指offer3 从尾到头打印链表

单项列表结构体

struct ListNode 
{
    int val;
    struct ListNode *next;
};

C++解题

思路1：利用vector的push_back()插入后，再遍历使得前后反转

运行时间：4ms 占用内存：504k

代码如下：

class Solution 
{
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        vector<int> ArrayList;
        ListNode* p = head; // 防止head丢失
        while (p)
        {
            ArrayList.push_back(p->val);
            p = p->next;
        }
        // for(int i = 0; i < ArrayList.size() / 2; i++) 和下方循环效果相同
        for (int i = 0; i < ArrayList.size() - i; i++)
        {
            int tmp = ArrayList[i];
            ArrayList[i] = ArrayList[ArrayList.size() - 1 - i];
            ArrayList[ArrayList.size() - 1 - i] = tmp;

        }
        return ArrayList;
    }
};

复杂度分析：遍历链表复杂度为n，遍历vector复杂度也为n，所以总的时间复杂度为

思路2：利用vector的vector.insert(vector.begin(),x)从第一个元素前方插入元素，省去反转过程

运行时间：3ms 占用内存：456k

代码如下：

class Solution 
{
public:
    vector<int> printListFromTailToHead(ListNode* head) 
    {
        vector<int> ArrayList;
        ListNode* p = head;
        if (p != NULL) // 首先要保证head指针不为空
        {
            ArrayList.insert(ArrayList.begin(), p->val); // 在第0个位置之前插入值
            while (p->next != NULL) // 这里要保证head的子节点不为空
            {
                ArrayList.insert(ArrayList.begin(), p->next->val); // 这里添加的元素是子节点的值，而非当前节点的值
                p = p->next;
            }
        }
        return ArrayList;
    }
};

复杂度分析：时间复杂度

思路3：创建额外的stack，存入stack后在正向pop出来

运行时间：4ms 占用内存：452k

代码如下：

class Solution 
{
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        vector<int> ArrayList;
        stack<int> tmp;
        ListNode* p = head; // 防止head丢失
        while (p != NULL)
        {
            tmp.push(p->val);
            p = p->next;
        }
        int size = tmp.size();
        for (int i = 0; i < size; i++)
        {
            ArrayList.push_back(tmp.top()); //stack.top()取栈顶值
            tmp.pop(); // 移除栈顶值
        }
        return ArrayList;
    }
};

复杂度分析：时间复杂度，运用额外的空间

知识点总结

1. 单向链表的创建和遍历
2. vector的运用，push_back(), insert()
3. stack的运用，push(), size(), top(), pop()