刷算法题:
第一遍: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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
3.思路的异同
因为这几天一直在刷反转链表的题目,所以就惯性思维了。但是这个题目与平常的反转链表相比,返回的是一个容器。
第二个例子说明,递归的本质就是一个栈,先进后出。太优雅了。
三.进步的地方
题目中选择使用辅助栈的方法,借用栈天生的先进后出实现反转。
同时也学到了怎么使用栈的pop、empty、top等关键字。