鏈表反轉(zhuǎn)實現(xiàn)方法，后一種擊敗了100%的用戶！

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

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

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

題目

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

描述：定義一個函數(shù)，輸入一個鏈表的頭節(jié)點，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(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ù)結(jié)構(gòu)，因此它的執(zhí)行過程如下圖所示：

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

實現(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; // 指針移動的下一位
    }
    // 反轉(zhuǎn)鏈表
    ListNode listNode = stack.pop(); // 反轉(zhuǎn)第一個元素
    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 驗證結(jié)果如下圖所示：

實現(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; // 設(shè)置下一個節(jié)點的 next 為當前節(jié)點
    head.next = null; // 把當前節(jié)點的 next 賦值為 null，避免循環(huán)引用
    return reverse;
}

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

總結(jié)

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

文章來源于公眾號：Java中文社群，作者：磊哥

以上就是W3Cschool編程獅關(guān)于鏈表反轉(zhuǎn)實現(xiàn)方法，后一種擊敗了100%的用戶！的相關(guān)介紹了，希望對大家有所幫助。