作者 | 王磊

來(lái)源 | Java中文社群（ID：javacn666）

轉(zhuǎn)載請(qǐng)聯(lián)系授權(quán)（微信ID：GG_Stone）

鏈表反轉(zhuǎn)是一道很基礎(chǔ)但又非常熱門的算法面試題，它也在《劍指Offer》的第 24 道題出現(xiàn)過(guò)，至于它有多熱（門）看下面的榜單就知道了。

從牛客網(wǎng)的數(shù)據(jù)來(lái)看，鏈表反轉(zhuǎn)的面試題分別霸占了【上周考過(guò)】和【研發(fā)最愛(ài)考】的雙重榜單，像網(wǎng)易、字節(jié)等知名互聯(lián)網(wǎng)公司都考過(guò)，但通過(guò)率卻低的只有 30%，所以本文我們就來(lái)學(xué)習(xí)一下反轉(zhuǎn)鏈表的兩種實(shí)現(xiàn)方法。

排行榜數(shù)據(jù)：https://www.nowcoder.com/activity/oj

題目

標(biāo)題：劍指 Offer 24. 反轉(zhuǎn)鏈表

描述：定義一個(gè)函數(shù)，輸入一個(gè)鏈表的頭節(jié)點(diǎn)，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)。

示例:

輸入: 1->2->3->4->5->NULL

輸出: 5->4->3->2->1->NULL

LeetCode 鏈接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

實(shí)現(xiàn)方式一：Stack

全部入棧：

因?yàn)闂Ｊ窍冗M(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，因此它的執(zhí)行過(guò)程如下圖所示：

最終的執(zhí)行結(jié)果如下圖所示：

實(shí)現(xiàn)代碼如下所示：

public?ListNode?reverseList(ListNode?head)?{if?(head?==?null)?return?null;Stack<ListNode>?stack?=?new?Stack<>();stack.push(head);?//?存入第一個(gè)節(jié)點(diǎn)while?(head.next?!=?null)?{stack.push(head.next);?//?存入其他節(jié)點(diǎn)head?=?head.next;?//?指針移動(dòng)的下一位}//?反轉(zhuǎn)鏈表ListNode?listNode?=?stack.pop();?//?反轉(zhuǎn)第一個(gè)元素ListNode?lastNode?=?listNode;?//?臨時(shí)節(jié)點(diǎn)，在下面的?while?中記錄上一個(gè)節(jié)點(diǎn)while?(!stack.isEmpty())?{ListNode?item?=?stack.pop();?//?當(dāng)前節(jié)點(diǎn)lastNode.next?=?item;lastNode?=?item;}lastNode.next?=?null;?//?最后一個(gè)節(jié)點(diǎn)賦為null（不然會(huì)造成死循環(huán)）return?listNode; }

LeetCode 驗(yàn)證結(jié)果如下圖所示：

實(shí)現(xiàn)方式二：遞歸

實(shí)現(xiàn)代碼如下所示：

public?static?ListNode?reverseList(ListNode?head)?{if?(head?==?null?||?head.next?==?null)?return?head;//?從下一個(gè)節(jié)點(diǎn)開(kāi)始遞歸ListNode?reverse?=?reverseList(head.next);head.next.next?=?head;?//?設(shè)置下一個(gè)節(jié)點(diǎn)的?next?為當(dāng)前節(jié)點(diǎn)head.next?=?null;?//?把當(dāng)前節(jié)點(diǎn)的?next?賦值為?null，避免循環(huán)引用return?reverse; }

LeetCode 驗(yàn)證結(jié)果如下圖所示：

總結(jié)

本文我們分別使用了 Stack?和遞歸的方法實(shí)現(xiàn)了鏈表反轉(zhuǎn)的功能，其中 Stack?的實(shí)現(xiàn)方式是利用了棧后進(jìn)先出的特性可以直接對(duì)鏈表進(jìn)行反轉(zhuǎn)，實(shí)現(xiàn)思路和實(shí)現(xiàn)代碼都比較簡(jiǎn)單，但在性能和內(nèi)存消耗方面都不是很理想，可以作為筆試的保底實(shí)現(xiàn)方案；而遞歸的方式在性能和內(nèi)存消耗方面都有良好的表現(xiàn)，同時(shí)它的實(shí)現(xiàn)代碼也很簡(jiǎn)潔，讀者只需理解代碼實(shí)現(xiàn)的思路即可。

往期推薦

JDK 竟然是這樣實(shí)現(xiàn)棧的？

動(dòng)圖演示：手?jǐn)]堆棧的兩種實(shí)現(xiàn)方法！

漫畫(huà)：什么是紅黑樹(shù)？（整合版）

關(guān)注下方二維碼，收獲更多干貨！

總結(jié)

以上是生活随笔為你收集整理的链表反转的两种实现方法，后一种击败了100%的用户！的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。