關(guān)注、星標(biāo)下方公眾號(hào)，和你一起成長(zhǎng)
(資料圖片)
作者 | 梁唐
出品 | 公眾號(hào)：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
今天我們繼續(xù)來(lái)挑戰(zhàn)鏈表，來(lái)看一道LeetCode當(dāng)中的一道經(jīng)典問(wèn)題——206.反轉(zhuǎn)鏈表。
這道題在很多公司的面試和筆試題中都有出現(xiàn)，我就曾經(jīng)遇到過(guò)。絕對(duì)算是鏈表領(lǐng)域的經(jīng)典例題了，如果最近剛好要參加面試筆試的同學(xué)，那么千萬(wàn)不要錯(cuò)過(guò)，說(shuō)不定就遇上了。
我們先來(lái)看看題面。
206. 反轉(zhuǎn)鏈表
給你單鏈表的頭節(jié)點(diǎn) head，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
分析
題面還是比較直接的，就是讓我們將一個(gè)給定的鏈表來(lái)翻轉(zhuǎn)。
最簡(jiǎn)單最取巧的方法當(dāng)然是先遍歷一遍鏈表，將所有元素存進(jìn)數(shù)組之后，再認(rèn)為構(gòu)造一個(gè)鏈表。這樣做當(dāng)然不能說(shuō)不行，只不過(guò)在面試當(dāng)中通常是無(wú)法令面試官滿意的。
因?yàn)槲覀兏緵](méi)有利用好給定我們的鏈表，額外地消耗了內(nèi)存空間。所以如果在面試當(dāng)中遇到，面試官是不會(huì)只滿足于聽到這樣的回答的。那么，我們又該如何在不創(chuàng)建新鏈表的前提下完成翻轉(zhuǎn)呢？
對(duì)于這個(gè)問(wèn)題，這題很好心地在進(jìn)階里面給了我們提示，可以使用迭代或者遞歸的方法。
我個(gè)人感覺(jué)這兩種方法難度差不多，不過(guò)從理解難度上來(lái)說(shuō)，遞歸的方法更簡(jiǎn)單直觀一些。
遞歸法
為什么說(shuō)遞歸的方法稍微更直觀呢？因?yàn)槲覀兛梢园堰f歸函數(shù)本身當(dāng)成是一個(gè)能夠在更小范圍內(nèi)運(yùn)作的黑盒，接著，我們要做的就是像是套娃一樣，讓它能夠在更大的范圍當(dāng)中實(shí)現(xiàn)同樣的功能。
比如在這題當(dāng)中，我們要使用遞歸來(lái)實(shí)現(xiàn)reverseList函數(shù)。我們先假設(shè)，它能夠在比當(dāng)前更小的范圍內(nèi)運(yùn)行。對(duì)于當(dāng)前輸入來(lái)說(shuō)是head開頭的鏈表，那么head->next開頭的鏈表就可以看成是比當(dāng)前范圍更小的范圍。我們假設(shè)reverseList能夠?qū)?code>head->next開頭的鏈表翻轉(zhuǎn)，我們要在此基礎(chǔ)上構(gòu)造出以head開頭翻轉(zhuǎn)的結(jié)果。
假設(shè)當(dāng)前的輸入是[1, 2, 3, 4, 5]，當(dāng)前head指向1。head->next指向[2, 3, 4, 5]。調(diào)用reverseList之后可以得到[5, 4, 3, 2]。所以我們要做的把head放到遞歸結(jié)果的末尾。
所以我們要做的就很簡(jiǎn)單，只有兩步。第一步遞歸調(diào)用reverseList，傳入head->next拿到結(jié)果。第二步，將head插入到遞歸返回的鏈表末尾。
由于在本題中鏈表都是通過(guò)頭節(jié)點(diǎn)表示的，所以我們要先遍歷一次到達(dá)鏈表的結(jié)尾。不要忘了處理一下邊界情況，即head為空或者是head->next為空的情況。
這些都想明白的話，代碼自然也就出來(lái)了：
classSolution{public:ListNode*reverseList(ListNode*head){//處理邊界if(head==nullptr||head->next==nullptr)returnhead;//遞歸調(diào)用autocur=reverseList(head->next);//遍歷到鏈表的最后一個(gè)節(jié)點(diǎn)autotmp=cur;while(tmp->next!=nullptr)tmp=tmp->next;//插入headtmp->next=head;head->next=nullptr;returncur;}};改進(jìn)
這里我們?yōu)榱饲蟪鲦湵碜詈笠粋€(gè)節(jié)點(diǎn)在遞歸當(dāng)中使用了循環(huán)，通過(guò)遍歷的方式去找了最末的節(jié)點(diǎn)。
實(shí)際上我們大可以不必如此，我們直接讓遞歸函數(shù)也返回末尾的指針即可。但這樣的話，我們就修改了返回值的類型，所以就要單獨(dú)寫一個(gè)遞歸來(lái)實(shí)現(xiàn)了。整體的原理和剛才是一樣的，只不過(guò)我們稍作加工，讓遞歸能夠既返回頭節(jié)點(diǎn)也返回尾節(jié)點(diǎn)。我們就不用再去額外遍歷了。
下面這段代碼的核心邏輯和之前是一樣的，只是優(yōu)化了遞歸返回的部分。
classSolution{public:pairreverse(ListNode*head){//處理邊界if(head==nullptr||head->next==nullptr)returnmake_pair(head,head);//遞歸autotmp=reverse(head->next);//將head插入到末尾tmp.second->next=head;head->next=nullptr;//返回新結(jié)果returnmake_pair(tmp.first,head);}ListNode*reverseList(ListNode*head){returnreverse(head).first;}}; 迭代
理解完了遞歸的做法之后，我們?cè)賮?lái)思考：如果不使用遞歸，那么這道題又該怎么解決呢？
其實(shí)并不難，只需要理解一點(diǎn)就可以搞定。那就是對(duì)于鏈表來(lái)說(shuō)，我們可以在任何節(jié)點(diǎn)插入元素。既然如此，我們既可以每次插入在末尾，自然也可以插入在頭部。如果我們每次插入元素都在頭部的話，得到的鏈表中的元素順序剛好和之前相反。
所以我們只需要再創(chuàng)建一個(gè)鏈表，一邊遍歷，一邊將讀取到的元素插入在新鏈表的頭部，最后返回即可。
這里可以使用之前介紹的虛擬頭節(jié)點(diǎn)的技巧來(lái)簡(jiǎn)化代碼：
classSolution{public:ListNode*reverseList(ListNode*head){if(head==nullptr)returnhead;autopt=head;//新鏈表的虛擬頭節(jié)點(diǎn)autoret=newListNode(0);while(pt!=nullptr){autocur=pt;pt=pt->next;//插入在ret指針之后cur->next=ret->next;ret->next=cur;}returnret->next;}};這道題雖然難度不大，但是正解的兩種方法都需要對(duì)鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)本身的特點(diǎn)有比較深入的理解以及一定的代碼能力才能通過(guò)。除了這題之外，還有LeetCode19 刪除鏈表倒數(shù)第n個(gè)元素這題也非常不錯(cuò)。我個(gè)人認(rèn)為不如這題經(jīng)典，所以就不過(guò)多贅述了，感興趣的同學(xué)可以自己去找來(lái)練習(xí)一下。
感謝大家的閱讀，如果喜歡的話，懇請(qǐng)幫忙轉(zhuǎn)發(fā)擴(kuò)散。算法學(xué)習(xí)之旅，與你同行。
喜歡本文的話不要忘記三連~