关于leetcode:每日一练3从尾到头打印链表

title: 每日一练（3）：从尾到头打印链表

categories:[剑指offer]

tags:[每日一练]

date: 2022/01/14

每日一练（3）：从尾到头打印链表

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

示例 1：

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

限度：

0 <= 链表长度 <= 10000

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl...

办法一：遍历反转

算法流程：

• 先遍历一遍获取链表大小
• 从新遍历，将数据insert到arr容器里

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    vector<int> reversePrint(ListNode* head) {        int len = 0;        ListNode *node = head;        while (node != NULL) {            len++;     //失去数据的长度            node = node->next;        }         vector<int> arr;         ListNode *p = head;        for (int i = 0; i < len; i++) {            arr.insert(arr.begin(), p->val);     //insert倒插            p = p->next;        }        return arr;    }};

办法二：应用栈先进后出

算法流程：

• 入栈： 遍历链表，将各节点值 push 入栈。
• 出栈： 将各节点值 pop 出栈，存储于数组并返回。

复杂度剖析：

• 工夫复杂度 O(N)： 入栈和出栈共应用 O(N) 工夫。
• 空间复杂度 O(N)： 辅助栈 stack 和数组 res 共应用 O(N)的额定空间。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    vector<int> reversePrint(ListNode* head) {        stack<int> s;        vector<int> res;        ListNode *p = head;        while(p != NULL)        {            s.push(p->val); //节点数据顺次入栈            p = p->next;        }        while(!s.empty()) //遍历栈        {            res.push_back(s.top()); //反转            s.pop();        }        return res;    }};