关于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;
    }
};