關注、星標下方公眾號，和你一起成長

(資料圖片)

作者 | 梁唐

出品 | 公眾號：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天我們繼續來挑戰鏈表，來看一道LeetCode當中的一道經典問題——206.反轉鏈表。

這道題在很多公司的面試和筆試題中都有出現，我就曾經遇到過。絕對算是鏈表領域的經典例題了，如果最近剛好要參加面試筆試的同學，那么千萬不要錯過，說不定就遇上了。

我們先來看看題面。

206. 反轉鏈表

給你單鏈表的頭節點 head，請你反轉鏈表，并返回反轉后的鏈表。

分析

題面還是比較直接的，就是讓我們將一個給定的鏈表來翻轉。

最簡單最取巧的方法當然是先遍歷一遍鏈表，將所有元素存進數組之后，再認為構造一個鏈表。這樣做當然不能說不行，只不過在面試當中通常是無法令面試官滿意的。

因為我們根本沒有利用好給定我們的鏈表，額外地消耗了內存空間。所以如果在面試當中遇到，面試官是不會只滿足于聽到這樣的回答的。那么，我們又該如何在不創建新鏈表的前提下完成翻轉呢？

對于這個問題，這題很好心地在進階里面給了我們提示，可以使用迭代或者遞歸的方法。

我個人感覺這兩種方法難度差不多，不過從理解難度上來說，遞歸的方法更簡單直觀一些。

遞歸法

為什么說遞歸的方法稍微更直觀呢？因為我們可以把遞歸函數本身當成是一個能夠在更小范圍內運作的黑盒，接著，我們要做的就是像是套娃一樣，讓它能夠在更大的范圍當中實現同樣的功能。

比如在這題當中，我們要使用遞歸來實現reverseList函數。我們先假設，它能夠在比當前更小的范圍內運行。對于當前輸入來說是head開頭的鏈表，那么head->next開頭的鏈表就可以看成是比當前范圍更小的范圍。我們假設reverseList能夠將head->next開頭的鏈表翻轉，我們要在此基礎上構造出以head開頭翻轉的結果。

假設當前的輸入是[1, 2, 3, 4, 5]，當前head指向1。head->next指向[2, 3, 4, 5]。調用reverseList之后可以得到[5, 4, 3, 2]。所以我們要做的把head放到遞歸結果的末尾。

所以我們要做的就很簡單，只有兩步。第一步遞歸調用reverseList，傳入head->next拿到結果。第二步，將head插入到遞歸返回的鏈表末尾。

由于在本題中鏈表都是通過頭節點表示的，所以我們要先遍歷一次到達鏈表的結尾。不要忘了處理一下邊界情況，即head為空或者是head->next為空的情況。

這些都想明白的話，代碼自然也就出來了：

classSolution{public:ListNode*reverseList(ListNode*head){//處理邊界if(head==nullptr||head->next==nullptr)returnhead;//遞歸調用autocur=reverseList(head->next);//遍歷到鏈表的最后一個節點autotmp=cur;while(tmp->next!=nullptr)tmp=tmp->next;//插入headtmp->next=head;head->next=nullptr;returncur;}};

改進

這里我們為了求出鏈表最后一個節點在遞歸當中使用了循環，通過遍歷的方式去找了最末的節點。

實際上我們大可以不必如此，我們直接讓遞歸函數也返回末尾的指針即可。但這樣的話，我們就修改了返回值的類型，所以就要單獨寫一個遞歸來實現了。整體的原理和剛才是一樣的，只不過我們稍作加工，讓遞歸能夠既返回頭節點也返回尾節點。我們就不用再去額外遍歷了。

下面這段代碼的核心邏輯和之前是一樣的，只是優化了遞歸返回的部分。

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;//返回新結果returnmake_pair(tmp.first,head);}ListNode*reverseList(ListNode*head){returnreverse(head).first;}};

迭代

理解完了遞歸的做法之后，我們再來思考：如果不使用遞歸，那么這道題又該怎么解決呢？

其實并不難，只需要理解一點就可以搞定。那就是對于鏈表來說，我們可以在任何節點插入元素。既然如此，我們既可以每次插入在末尾，自然也可以插入在頭部。如果我們每次插入元素都在頭部的話，得到的鏈表中的元素順序剛好和之前相反。

所以我們只需要再創建一個鏈表，一邊遍歷，一邊將讀取到的元素插入在新鏈表的頭部，最后返回即可。

這里可以使用之前介紹的虛擬頭節點的技巧來簡化代碼：

classSolution{public:ListNode*reverseList(ListNode*head){if(head==nullptr)returnhead;autopt=head;//新鏈表的虛擬頭節點autoret=newListNode(0);while(pt!=nullptr){autocur=pt;pt=pt->next;//插入在ret指針之后cur->next=ret->next;ret->next=cur;}returnret->next;}};

這道題雖然難度不大，但是正解的兩種方法都需要對鏈表這個數據結構本身的特點有比較深入的理解以及一定的代碼能力才能通過。除了這題之外，還有LeetCode19 刪除鏈表倒數第n個元素這題也非常不錯。我個人認為不如這題經典，所以就不過多贅述了，感興趣的同學可以自己去找來練習一下。

感謝大家的閱讀，如果喜歡的話，懇請幫忙轉發擴散。算法學習之旅，與你同行。

喜歡本文的話不要忘記三連~