鏈表反轉是一道很基礎但又非常熱門的算法面試題,它也在《劍指Offer》的第 24 道題出現(xiàn)過,至于它有多熱(門)看下面的榜單就知道了。
從??途W(wǎng)的數(shù)據(jù)來看,鏈表反轉的面試題分別霸占了【上周考過】和【研發(fā)最愛考】的雙重榜單,像網(wǎng)易、字節(jié)等知名互聯(lián)網(wǎng)公司都考過,但通過率卻低的只有 30%,所以本文我們就來學習一下反轉鏈表的兩種實現(xiàn)方法。
排行榜數(shù)據(jù):https://www.nowcoder.com/activity/oj
題目
標題:劍指 Offer 24. 反轉鏈表
描述:定義一個函數(shù),輸入一個鏈表的頭節(jié)點,反轉該鏈表并輸出反轉后鏈表的頭節(jié)點。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
LeetCode 鏈接:https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
實現(xiàn)方式一:Stack
全部入棧:
因為棧是先進后出的數(shù)據(jù)結構,因此它的執(zhí)行過程如下圖所示:
最終的執(zhí)行結果如下圖所示:
實現(xiàn)代碼如下所示:
public ListNode reverseList(ListNode head) {
if (head == null) return null;
Stack stack = new Stack();
stack.push(head); // 存入第一個節(jié)點
while (head.next != null) {
stack.push(head.next); // 存入其他節(jié)點
head = head.next; // 指針移動的下一位
}
// 反轉鏈表
ListNode listNode = stack.pop(); // 反轉第一個元素
ListNode lastNode = listNode; // 臨時節(jié)點,在下面的 while 中記錄上一個節(jié)點
while (!stack.isEmpty()) {
ListNode item = stack.pop(); // 當前節(jié)點
lastNode.next = item;
lastNode = item;
}
lastNode.next = null; // 最后一個節(jié)點賦為null(不然會造成死循環(huán))
return listNode;
}
LeetCode 驗證結果如下圖所示:
實現(xiàn)方式二:遞歸
實現(xiàn)代碼如下所示:
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
// 從下一個節(jié)點開始遞歸
ListNode reverse = reverseList(head.next);
head.next.next = head; // 設置下一個節(jié)點的 next 為當前節(jié)點
head.next = null; // 把當前節(jié)點的 next 賦值為 null,避免循環(huán)引用
return reverse;
}
LeetCode 驗證結果如下圖所示:
總結
本文我們分別使用了 Stack
和遞歸的方法實現(xiàn)了鏈表反轉的功能,其中 Stack
的實現(xiàn)方式是利用了棧后進先出的特性可以直接對鏈表進行反轉,實現(xiàn)思路和實現(xiàn)代碼都比較簡單,但在性能和內(nèi)存消耗方面都不是很理想,可以作為筆試的保底實現(xiàn)方案;而遞歸的方式在性能和內(nèi)存消耗方面都有良好的表現(xiàn),同時它的實現(xiàn)代碼也很簡潔,讀者只需理解代碼實現(xiàn)的思路即可。
文章來源于公眾號:Java中文社群,作者:磊哥
以上就是W3Cschool編程獅
關于鏈表反轉實現(xiàn)方法,后一種擊敗了100%的用戶!的相關介紹了,希望對大家有所幫助。