06.从尾到头打印链表 (Easy)*

题目描述*

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

示例*

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

输出：[2,3,1]

限制*

0 <= 链表长度 <= 10000

代码*

大概几种做法：反转链表、栈、头插法等。

迭代反转链表头插法栈

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        ListNode *slow = nullptr, *fast = head;
        while(fast != nullptr) {
            ListNode *p = fast->next;
            fast->next = slow;
            slow = fast;
            fast = p;
        }
        while(slow != nullptr) {
            res.push_back(slow->val);
            slow = slow->next;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        // 练习头插法
        ListNode *newHead = new ListNode(-1);
        while(head != nullptr) {
            ListNode *p = head->next;
            head->next = newHead->next;
            newHead->next = head;
            head = p;
        }
        head = newHead->next;
        while(head != nullptr) {
            res.push_back(head->val);
            head = head->next;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        stack<int> st;
        while(head != nullptr) {
            st.push(head->val);
            head = head->next;
        }
        while(!st.empty()) {
            res.push_back(st.top());
            st.pop();
        }
        return res;
    }
};

最后更新: July 23, 2022