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