當我們在聊到鏈表反轉的時候，一定說的都是單鏈表，雙鏈表本身就具有前驅指針 Prev 和后續指針 next，無需進行翻轉。

單鏈表反轉，反轉后的效果如下：

看起來很簡單，只需要將單鏈表所有結點的 next 指向，指向它的前驅節點即可。引入一個棧結構，就可以實現。

棧實現的鏈表反轉

在原本鏈表的數據結構之外，引入一個棧（數組也可），將單鏈表循環遍歷，將所有結點入棧，最后再從棧中循環出棧，繼續出棧的順序，得到的就是反轉后的單鏈表。

但是這樣實現，有一個問題，它會額外消耗一個棧的內存空間，此時空間復雜度就變成了 O(n)。并且，棧會遇到的問題，使用此種方式都會遇到，例如棧的深度問題。

空間復雜度為 O(1) 單鏈表反轉

在排序算法中，有一個概念叫原地排序，指的是不需要引入額外的存儲空間，在原數據結構的基礎上進行排序。這種排序算法的空間復雜度是 O(1)。例如我們常見的冒泡排序、插入排序都是原地排序算法。

這里，我們也可以在原單鏈表的數據結構上，進行單鏈表反轉。

原地單鏈表反轉，是一種很基礎的算法，但是有一些在面試中遇到這道題，思路不清晰時，一時半會也寫不出來。

容易出錯的點在于，指針丟失。在轉換結點指針的時候，所需結點和指針反轉順序，都很重要，一不小心，就會丟掉原本的后續指針 next，導致鏈表斷裂。

在上一篇文章中，帶單鏈表時間復雜度為 O(1) 的結點刪除法中，介紹到，刪除單鏈表的時候，需要知道前后三個結點。在單鏈表翻轉的時候，也是這樣。

當我們要對一個結點進行指針翻轉的時候，我們也需要知道三個結點。

• 待翻轉的結點。
• 待反轉結點的前驅結點 prev。
• 待反轉結點的后續結點 next。

說了那么多，直接上代碼。

static class Node {
 int data;
 Node next;
 Node(int data){
 this.data = data;
 }
}
static Node reverseByLoop(Node head) {
 if (head == null || head.next == null){
 return head;
 }
 Node preNode = null;
 Node nextNode = null;
 while (head != null){
 nextNode = head.next;
 head.next = preNode;
 preNode = head;
 head = nextNode;
 }
 return preNode;
}

鏈表翻轉的所有邏輯，都在 reverseByLoop() 方法中，此處以頭結點為參數，反轉之后返回值為反轉后的單鏈表頭結點。

有興趣最好自己在 IDE 里敲一遍，加深印象。

遞歸實現單鏈表翻轉

單鏈表翻轉，還可以通過遞歸來實現，但是這里不推薦使用，大家了解一下就好了。

遞歸還是在借助函數調用棧的思想，其實本質上也是一個棧。沒什么好說的，直接上代碼。

static Node reverseByRecursion(Node head){
 if(head == null || head.next == null){
 return head;
 }
 Node newHead = reverseByRecursion(head.next);
 head.next.next = head;
 head.next = null;
 return newHead;
}

小結時刻

到這里，單鏈表反轉的內容，都介紹完了，學算法還是要考慮多寫多練，推薦大家在 IDE 中，自己手動敲一遍，加深印象。

本文對你有幫助嗎？留言、點贊、轉發是最大的支持，謝謝！