當我們在聊到鏈表反轉(zhuǎn)的時候，一定說的都是單鏈表，雙鏈表本身就具有前驅(qū)指針 Prev 和后續(xù)指針 next，無需進行翻轉(zhuǎn)。
單鏈表反轉(zhuǎn)，反轉(zhuǎn)后的效果如下：
看起來很簡單，只需要將單鏈表所有結(jié)點的 next 指向，指向它的前驅(qū)節(jié)點即可。引入一個棧結(jié)構(gòu)，就可以實現(xiàn)。
棧實現(xiàn)的鏈表反轉(zhuǎn)
在原本鏈表的數(shù)據(jù)結(jié)構(gòu)之外，引入一個棧（數(shù)組也可），將單鏈表循環(huán)遍歷，將所有結(jié)點入棧，最后再從棧中循環(huán)出棧，繼續(xù)出棧的順序，得到的就是反轉(zhuǎn)后的單鏈表。
但是這樣實現(xiàn)，有一個問題，它會額外消耗一個棧的內(nèi)存空間，此時空間復雜度就變成了 O(n)。并且，棧會遇到的問題，使用此種方式都會遇到，例如棧的深度問題。
空間復雜度為 O(1) 單鏈表反轉(zhuǎn)
在排序算法中，有一個概念叫原地排序，指的是不需要引入額外的存儲空間，在原數(shù)據(jù)結(jié)構(gòu)的基礎上進行排序。這種排序算法的空間復雜度是 O(1)。例如我們常見的冒泡排序、插入排序都是原地排序算法。
這里，我們也可以在原單鏈表的數(shù)據(jù)結(jié)構(gòu)上，進行單鏈表反轉(zhuǎn)。
原地單鏈表反轉(zhuǎn)，是一種很基礎的算法，但是有一些在面試中遇到這道題，思路不清晰時，一時半會也寫不出來。
容易出錯的點在于，指針丟失。在轉(zhuǎn)換結(jié)點指針的時候，所需結(jié)點和指針反轉(zhuǎn)順序，都很重要，一不小心，就會丟掉原本的后續(xù)指針 next，導致鏈表斷裂。
在上一篇文章中，帶單鏈表時間復雜度為 O(1) 的結(jié)點刪除法中，介紹到，刪除單鏈表的時候，需要知道前后三個結(jié)點。在單鏈表翻轉(zhuǎn)的時候，也是這樣。
當我們要對一個結(jié)點進行指針翻轉(zhuǎn)的時候，我們也需要知道三個結(jié)點。
- 待翻轉(zhuǎn)的結(jié)點。
- 待反轉(zhuǎn)結(jié)點的前驅(qū)結(jié)點 prev。
- 待反轉(zhuǎn)結(jié)點的后續(xù)結(jié)點 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;
}
鏈表翻轉(zhuǎn)的所有邏輯，都在 reverseByLoop() 方法中，此處以頭結(jié)點為參數(shù)，反轉(zhuǎn)之后返回值為反轉(zhuǎn)后的單鏈表頭結(jié)點。
有興趣最好自己在 IDE 里敲一遍，加深印象。
遞歸實現(xiàn)單鏈表翻轉(zhuǎn)
單鏈表翻轉(zhuǎn)，還可以通過遞歸來實現(xiàn)，但是這里不推薦使用，大家了解一下就好了。
遞歸還是在借助函數(shù)調(diào)用棧的思想，其實本質(zhì)上也是一個棧。沒什么好說的，直接上代碼。
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;
}
小結(jié)時刻
到這里，單鏈表反轉(zhuǎn)的內(nèi)容，都介紹完了，學算法還是要考慮多寫多練，推薦大家在 IDE 中，自己手動敲一遍，加深印象。
本文對你有幫助嗎？留言、點贊、轉(zhuǎn)發(fā)是最大的支持，謝謝！
