LCR 123. 图书整理 I

刷算法题：

第一遍：1.看5分钟，没思路看题解

2.通过题解改进自己的解法，并且要写每行的注释以及自己的思路。

3.思考自己做到了题解的哪一步，下次怎么才能做对(总结方法)

4.整理到自己的自媒体平台。

5.再刷重复的类似的题目，根据时间和任务安排刷哪几个板块

6.用c++语言都刷过一遍了就刷中等

一.题目

书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。

示例 1

输入：head = [3,6,4,1]

输出：[1,4,6,3]

提示：

0 <= 链表长度 <= 10000

二、反思

1.自己的解法

/**
 * 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 {
public:
    vector<int> reverseBookList(ListNode* head) {
        ListNode* cur=head;
        ListNode* pre=nullptr;
        vector <int> res;
        while (cur){
            ListNode* next =cur->next;
            cur->next=pre;
            pre =cur;
            cur = next;
        }
        while (pre){
            res.push_back(pre->val);
            pre=pre->next;
        }
        return res;
    }
};

2.题目的解法

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

作者：Krahets
链接：https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solutions/97270/mian-shi-ti-06-cong-wei-dao-tou-da-yin-lian-biao-d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    vector<int> reverseBookList(ListNode* head) {
        recur(head);
        return res;
    }
private:
    vector<int> res;
    void recur(ListNode* head) {
        if(head == nullptr) return;
        recur(head->next);//递归的本质就是一个栈，先进后出。
        res.push_back(head->val);
    }
};

作者：Krahets
链接：https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solutions/97270/mian-shi-ti-06-cong-wei-dao-tou-da-yin-lian-biao-d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。