【一刷《剑指Offer》】面试题 5：从尾到头打印链表

本文主要是介绍【一刷《剑指Offer》】面试题 5：从尾到头打印链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣对应链接：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;}
};

这篇关于【一刷《剑指Offer》】面试题 5：从尾到头打印链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---