2021.5.28剑指offer做题记录：06. 从尾到头打印链表(C++实现，栈，递归，数组等含代码）

剑指offer做题记录：06. 从尾到头打印链表(C++实现，栈，递归，数组等含代码）

链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

题目描述：

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例1：

输入：head = [1,3,2]
输出：[2,3,1]
           

限制：0 <= 链表长度 <= 10000

思路：

• 1.使用栈操作，可以将链表节点值直接添加进栈再遍历添加到数组中返回；
• 2.通过vector的reverse函数，将链表遍历后添加进arr数组，通过reverse(arr.begin(),arr.end());进行翻转然后返回；
• 3.通过vector的insert函数（慎！此方法执行耗时极大）遍历链表通过vector中自带的insert函数进行每次都在头插入新值然后返回数组；
• 4.通过递归，通过实现另一份递归方法找到链表尾结点进行添加进数组，之后递归全部完成直接返回即可；
• 5.通过迭代器反向遍历，首先遍历数组得到数量count，之后进行调用vector中rbegin函数反向取得元素的迭代器进行从数组尾遍历到头依次放入链表正遍历的值，返回数组；
• 以上思路代码实现如下所示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    //  //4.递归实现
    // void method(vector<int>& res,ListNode* head){
    //     if(head==NULL) return;
    //     method(res,head->next);
    //     res.push_back(head->val);
    // }

    vector<int> reversePrint(ListNode* head) {
        //1.通过栈操作
        vector<int> arr;
        stack<int> st;
        ListNode* pNode = head;
        while(pNode)
        {
            st.push(pNode->val);
            pNode = pNode->next;
        }
        while(!st.empty())
        {
            arr.push_back(st.top());
            st.pop();
        }
        return arr;


        //2.通过vector的reverse函数 执行用时： 4 ms , 在所有 C++ 提交中击败了 87.76% 的用户
        //内存消耗： 8.5 MB , 在所有 C++ 提交中击败了 67.45% 的用户

        // vector<int> arr;
        // ListNode *pNode = head;
        // while(pNode)
        // {
        //     arr.push_back(pNode->val);
        //     pNode = pNode->next;
        // }
        // reverse(arr.begin(),arr.end());
        // return arr;

        //3.通过vector的insert函数--不提倡  执行用时：
// 76 ms
// , 在所有 C++ 提交中击败了
// 6.50%
// 的用户
// 内存消耗：
// 8.5 MB
// , 在所有 C++ 提交中击败了
// 68.32%
// 的用户
    //     vector<int> arr;
    //     ListNode *pNode = head;
    //     while( pNode )
    //     {
    //         arr.insert(arr.begin(),pNode->val);
    //         pNode = pNode->next;
    //     }
    //     return arr;
     

    // //4.递归实现
    //     vector<int> res;
    //     method(res,head);
    //     return res;
    

  

    //5.通过迭代器遍历执行用时：
// 8 ms
// , 在所有 C++ 提交中击败了
// 42.89%
// 的用户
// 内存消耗：
// 8.4 MB
// , 在所有 C++ 提交中击败了
// 79.04%
// 的用户
    
    //  ListNode* pNode = head;
    // int count = 0;
    // while( pNode )
    // {
    //     ++count;
    //     pNode = pNode->next;
    // }
    // vector<int> arr(count);
    // pNode = head;
    // for(auto i = arr.rbegin(); i != arr.rend(); ++i)
    // {
    //     *i = pNode->val;
    //     pNode = pNode->next;
    // }
    // return arr ;
    


    }

};
           

记录完成OUO

此处就放个使用栈的执行结果:

(但其他方法也是好用的都测试过了，只是懒得截图了orz)

最后感谢观看OVO，欢迎点赞评论，留下自己想法大家可以互相交流~