自己怎么做團購網(wǎng)站優(yōu)化步驟
一、題目
二、本人思路及代碼
直接在鏈表里進行翻轉(zhuǎn)不太方便操作,但是數(shù)組就可以通過下標進行操作,于是,
思路1、
先遍歷鏈表,以此存到vector中,然后再從后往前遍歷這vector,存入到一個新的vector,就完成了翻轉(zhuǎn)操作。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:vector<int> printListFromTailToHead(ListNode* head) {vector<int> a,ret;while(head){a.push_back(head->val);head=head->next;}for(int i=a.size()-1;i>=0;i--){ret.push_back(a[i]);}return ret;}
};
思路2、
先遍歷鏈表,以此存到vector中,然后定義兩個指針,分別從頭部和尾部同時往中間遍歷,并將相應的位置進行交換,直到兩個指針相等或后面的指針小于前面的。例如{1,2,3,4,5} --> 1和5交換,2和4交換。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:vector<int> printListFromTailToHead(ListNode* head) {vector<int> a;while(head){a.push_back(head->val);head=head->next;}int i=0; int j=a.size()-1;int k;for(;i<j; j--,i++){k=a[i];a[i]=a[j];a[j]=k;}return a;}
};
三、學習他人精華
在牛客上看到一個思路,覺得非常不錯,記錄一下。
解法采用遞歸來實現(xiàn)鏈表的反轉(zhuǎn). 其實遞歸和反轉(zhuǎn)可以說是一對孿生兄弟, 遞歸在觸底反彈之后, 執(zhí)行的就是一個逆向的遍歷過程.
在函數(shù)外部聲明, 即把ret聲明為Solution類的一個公有變量. 從而函數(shù)每次直接調(diào)用ret執(zhí)行操作即可, 不需要在每一層遞歸都聲明一個新的ret.
class Solution {
public:vector<int> ret;vector<int> printListFromTailToHead(ListNode* head) {if(!head) return ret;printListFromTailToHead(head->next);ret.push_back(head->val);return ret;}
};