鏈表反轉的兩種實現方法，後一種擊敗了100%的用戶！

2020 年 10 月 13 日
筆記
core-java, JAVA

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

從牛客網的數據來看，鏈表反轉的面試題分別霸佔了【上周考過】和【研發最愛考】的雙重榜單，像網易、位元組等知名互聯網公司都考過，但通過率卻低的只有 30%，所以本文我們就來學習一下反轉鏈表的兩種實現方法。

排行榜數據：//www.nowcoder.com/activity/oj

題目

標題：劍指 Offer 24. 反轉鏈表

描述：定義一個函數，輸入一個鏈表的頭節點，反轉該鏈表並輸出反轉後鏈表的頭節點。

示例:

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

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

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

實現方式一：Stack

全部入棧：

因為棧是先進後出的數據結構，因此它的執行過程如下圖所示：

最終的執行結果如下圖所示：

實現程式碼如下所示：

public ListNode reverseList(ListNode head) {
    if (head == null) return null;
    Stack<ListNode> stack = new Stack<>();
    stack.push(head); // 存入第一個節點
    while (head.next != null) {
        stack.push(head.next); // 存入其他節點
        head = head.next; // 指針移動的下一位
    }
    // 反轉鏈表
    ListNode listNode = stack.pop(); // 反轉第一個元素
    ListNode lastNode = listNode; // 臨時節點，在下面的 while 中記錄上一個節點
    while (!stack.isEmpty()) {
        ListNode item = stack.pop(); // 當前節點
        lastNode.next = item;
        lastNode = item;
    }
    lastNode.next = null; // 最後一個節點賦為null（不然會造成死循環）
    return listNode;
}

LeetCode 驗證結果如下圖所示：

實現方式二：遞歸

實現程式碼如下所示：

public static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    // 從下一個節點開始遞歸
    ListNode reverse = reverseList(head.next);
    head.next.next = head; // 設置下一個節點的 next 為當前節點
    head.next = null; // 把當前節點的 next 賦值為 null，避免循環引用
    return reverse;
}

LeetCode 驗證結果如下圖所示：

總結

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

Tags: core-java JAVA