从头到尾打印链表

从头到尾打印链表，牛客网，leetcode。

本文记录了两种方法，并分别给出了两种方法的耗时以及耗时分析。

题目

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

方法1：

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

此种方法直接在新的vector的头部插入内容。vector底层使用数组实现，在尾部插入的时间复杂度为O(1)，在头部插入的时间复杂度为O(n)。因此本方法效率非常低。leetcode上时间为92ms。

方法2：

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> vec;
        if (head == nullptr) {
            return vec;
        }
        while (head != nullptr) {
            vec.push_back(head->val);
            head = head->next;
        }
        return vector<int>(vec.rbegin(), vec.rend());
    }
};

此种方法直接在vector队尾插入元素。返回一个使用逆序指针构建的数组。leetcode上时间为4ms。