力扣对应链接：LCR 123. 图书整理 I - 力扣（LeetCode）
牛客对应连接：从尾到头打印链表_牛客题霸_牛客网
核心考点 ：链表相关，多结构混合使用，递归。
一、《剑指Offer》内容
二、分析问题
这道题整体的解决思路很多，可以使用 stack，也可以将数据保存数组，再逆序数组，还可以递归。
三、代码
1、方法一（stack，但这种方式会有内存占用过多的问题）
//牛客代码 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { private: stack<int> st; vector<int> res; public: vector<int> printListFromTailToHead(ListNode* head) { while(head) { st.push(head->val); head=head->next; } while(st.size()) { res.push_back(st.top()); st.pop(); } return res; } }; //力扣代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { private: stack<int> st; vector<int> res; public: vector<int> reverseBookList(ListNode* head) { while(head) { st.push(head->val); head=head->next; } while(st.size()) { res.push_back(st.top()); st.pop(); } return res; } };
2、方法二（逆置数组）
//牛客代码 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { private: vector<int> res; public: vector<int> printListFromTailToHead(ListNode* head) { while(head) { res.push_back(head->val); head=head->next; } reverse(res.begin(), res.end()); return res; } }; //力扣代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { private: vector<int> res; public: vector<int> reverseBookList(ListNode* head) { while(head) { res.push_back(head->val); head=head->next; } reverse(res.begin(), res.end()); return res; } };
3、方法三（递归方式）
//牛客代码 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { private: vector<int> res; public: void reversePrint(ListNode* head) { if(head==nullptr) return; reversePrint(head->next); res.push_back(head->val); } vector<int> printListFromTailToHead(ListNode* head) { reversePrint(head); return res; } }; //力扣代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { private: vector<int> res; public: void reversePrint(ListNode* head) { if(head==nullptr) return; reversePrint(head->next); res.push_back(head->val); } vector<int> reverseBookList(ListNode* head) { reversePrint(head); return res; } };
