面試必備 | 不可不會(huì)的反轉(zhuǎn)鏈表

反轉(zhuǎn)鏈表這題真的是面試非常喜歡考的了，這題看起來(lái)簡(jiǎn)單，但是能用兩種方法一遍 bug free 也是不容易的，面試的時(shí)候可以篩下來(lái)一大批人，無(wú)論是對(duì) junior 還是 senior 面試都很愛(ài)考。

今天就帶你梳理清楚思路，思路清楚了才能寫碼如有神。

這是從力扣中文站上截下來(lái)的，但是這個(gè)輸出不太形象。

對(duì)鏈表的反轉(zhuǎn)，并不是要把它實(shí)際翻個(gè)個(gè)，只是動(dòng)一動(dòng) next 指針就好了。

什么意思呢？

我們先看對(duì)數(shù)組進(jìn)行反轉(zhuǎn)。

數(shù)組是一個(gè)物理上連續(xù)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，反轉(zhuǎn)之后原來(lái)放 1 的位置就變成了放 5.

但是鏈表并不是，因?yàn)殒湵碓谖锢砩鲜遣贿B續(xù)的，它的每個(gè)單元 ListNode 是通過(guò) next 指針連接在一起的，而每個(gè) ListNode 之間在內(nèi)存里并不一定是挨著的。

所以反轉(zhuǎn)鏈表，就不是非要把 1 的位置放 5，因?yàn)樗鼈兿朐谀脑谀摹?/p>

那么怎么保證這個(gè)順序呢？

• 就是 next 指針。

沿著 next 指針的方向走下去，就是鏈表的順序。這也就保證了，只要我們拿到了頭節(jié)點(diǎn)，就掌控了整個(gè) LinkedList.

那么題目中的例子，形象點(diǎn)是這個(gè)樣子滴：

也就是元素自己不用動(dòng)，只需要?jiǎng)觿?dòng)小指針，就是反轉(zhuǎn)了。

遞歸的三步驟大家還記得嗎？

Base case + 拆解 + 組合

不記得的趕緊在公眾號(hào)內(nèi)回復(fù)「遞歸」二字，獲取遞歸的入門篇詳解。

那么我們來(lái)看這個(gè)題的：

base case:

當(dāng)只有一個(gè) node，或者沒(méi)有 node 了唄，也就是

if(node?==?null?||?node.next?==?null)?{
??return?node;
}

其實(shí)呢，只剩一個(gè) node 的時(shí)候嚴(yán)格來(lái)講并不是 base case，而是 corner case，

因?yàn)樗究梢栽?break down 到 node == null 的，但因?yàn)楹竺嬗袑?duì) node.next 的 dereference 操作，所以不能省略。

拆解：

遞歸的拆解就是把大問(wèn)題，分解成小一點(diǎn)點(diǎn)的問(wèn)題，直到 base case 可以返回，進(jìn)行第三步的組合。

那么這里就是

組合：

組合的意思是，假設(shè)我們能夠拿到小問(wèn)題的解，那么用小問(wèn)題的解去構(gòu)造大問(wèn)題的解。

那么這道題如何構(gòu)造呢？

這里很明顯，在 2 后面接上 1 就行了。

但是怎么拿到 2 呢？

別忘了，原問(wèn)題里，此時(shí)還有 1 指向 2 呢～

也就是 node1.next = node2，

然后把 2 指向 1：node2.next = node1

合起來(lái)就是：node1.next.next = node1

思路清楚就不繞，看著覺(jué)得繞的就是沒(méi)想清楚哼～

代碼

遞歸的代碼寫起來(lái)都很簡(jiǎn)潔：

class?Solution?{
????public?ListNode?reverseList(ListNode?head)?{
????????if(head?==?null?||?head.next?==?null)?{
????????????return?head;
????????}
????????ListNode?newHead?=?reverseList(head.next);
????????head.next.next?=?head;
????????head.next?=?null;
????????return?newHead;
????}
}

時(shí)間復(fù)雜度

我們?cè)凇高f歸」這篇文章里說(shuō)過(guò)，遞歸的時(shí)間復(fù)雜度分析方法就是把遞歸樹(shù)畫出來(lái)，每個(gè)節(jié)點(diǎn)的時(shí)間加起來(lái)就行了。

這個(gè)遞歸樹(shù)是一個(gè)很簡(jiǎn)單的單項(xiàng)鏈表，每個(gè)節(jié)點(diǎn)上做的就是那三行代碼，也就是「組合」做的事，即 O(1) 的時(shí)間，總共有 n 個(gè)節(jié)點(diǎn)，那么總的時(shí)間就是 O(n).

空間復(fù)雜度

那看遞歸樹(shù)也很明顯了，每一層也就用了點(diǎn)小變量，是 O(1)，所以總的空間共是 O(n).

（誰(shuí)能告訴我這個(gè)中文的專業(yè)說(shuō)法。。

Iterative 的思路就是：
過(guò)一遍這個(gè) Linked List，邊過(guò)邊把這個(gè) node 的 next 指針指向前面那個(gè) node，直到過(guò)完全部。

這樣說(shuō)太抽象，面試時(shí)也是，直接過(guò)例子。

那也就是把 1 的 next 指針?lè)^(guò)來(lái)指向 NULL；
把 2 的 next 指針?lè)^(guò)來(lái)指向 1；
把 3 的 next 指針?lè)^(guò)來(lái)指向 2；
...

所以我們還需要一個(gè)變量來(lái)記錄當(dāng)前 node 的前一個(gè) node，不妨設(shè)為 prev.

同時(shí)呢，一旦我們把指針?lè)D(zhuǎn)過(guò)去，后面的那個(gè) node 就丟了有木有！所以還需要有個(gè)額外的變量事先記錄下后面的 node，設(shè)為 nxt，這樣才不至于走丟～

Step1.

翻轉(zhuǎn)箭頭：把 1 的 next 指針指向 NULL；

這樣子，同時(shí)我們也明確了，prev 的初始化應(yīng)該是 NULL.

然后把這仨變量都移動(dòng)到下一個(gè)位置：

Step2.

翻轉(zhuǎn)箭頭：把 2 的 next 指針指向 1，

然后三人行：

Step3.

翻轉(zhuǎn)箭頭：把 3 的 next 指針指向 2，

再齊步走：

Step4.

再把 4 的反過(guò)來(lái)：

再往后走：

Step5.

再把 5 的 next 反過(guò)來(lái)：

但是因?yàn)槲覀兊?while 循環(huán)包含了

「翻轉(zhuǎn)箭頭」+「三人行」

兩個(gè)步驟，所以還需要走完最后一個(gè)三人行，變成：

很多同學(xué)搞不清楚這個(gè) while 循環(huán)的結(jié)束條件，其實(shí)很簡(jiǎn)單，你就走個(gè)例子畫畫圖嘛！

那結(jié)束條件就是 curr = null 的時(shí)候，
最后返回的是 prev.

好了，看代碼吧：

class?Solution?{
????public?ListNode?reverseList(ListNode?head)?{
????????ListNode?prev?=?null;
????????ListNode?curr?=?head;

????????while(curr?!=?null)?{
????????????ListNode?nxt?=?curr.next;
????????????curr.next?=?prev;?//?翻轉(zhuǎn)箭頭
????????????prev?=?curr;?//三人行
????????????curr?=?nxt;?//三人行
????????}

????????return?prev;
????}
}

時(shí)間復(fù)雜度

這里的時(shí)間復(fù)雜度很明顯了，就是過(guò)了一遍這個(gè)鏈表，所以是 O(n).

空間復(fù)雜度

空間是 O(1).