當(dāng)我們談?wù)撴湵矸崔D(zhuǎn)時，我們必須說它們都是單鏈表，而雙鏈表本身具有前置指針Prev和下一個指針，而無需翻轉(zhuǎn).

單鏈表反轉(zhuǎn)，反轉(zhuǎn)后的效果如下:

這看起來非常簡單，只需指向單鏈表的所有節(jié)點中的下一個節(jié)點，然后指向其前任節(jié)點即可. 可以通過引入堆棧結(jié)構(gòu)來實現(xiàn).

除了原始鏈表的數(shù)據(jù)結(jié)構(gòu)外，還引入一個堆棧（也可以是數(shù)組），循環(huán)遍歷單鏈表，將所有節(jié)點放入堆棧中，最后從堆棧中循環(huán)出堆棧，請記住堆棧的順序，結(jié)果是一個反向的單鏈表.

但是此實現(xiàn)存在問題，它將消耗堆棧的額外存儲空間，并且空間復(fù)雜度變?yōu)镺（n）. 并且，堆棧遇到的問題將以這種方式遇到，例如堆棧深度更常見的問題.

接下來，我們看一下如何解決空間復(fù)雜性問題.

在排序算法中，有一個稱為就地排序的概念，它是指在原始數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上進(jìn)行排序而不引入額外的存儲空間. 該排序算法的空間復(fù)雜度為O（1）. 例如，我們常見的冒泡排序和插入排序是就地排序算法.

在這里，我們還可以在原始單鏈表的數(shù)據(jù)結(jié)構(gòu)上反轉(zhuǎn)單鏈表.

原位單鏈列表反轉(zhuǎn)是一個非常基本的算法，但是其中一些在采訪中遇到了這個問題. 如果這個主意不清楚，就不會寫成一個半.

容易出錯的地方是指針丟失. 轉(zhuǎn)換節(jié)點指針時，所需的節(jié)點和指針反轉(zhuǎn)順序非常重要. 如果您不小心，則會丟棄下一個原始后續(xù)指針，從而導(dǎo)致列表損壞.

在上一篇文章中鏈表反轉(zhuǎn) java，單鏈接列表時間復(fù)雜度為O（1）的節(jié)點刪除方法介紹了在刪除單鏈接列表時，您需要知道之前和之后的三個節(jié)點. 翻轉(zhuǎn)單鏈列表時也是如此.

當(dāng)我們想要翻轉(zhuǎn)一個節(jié)點的指針時，我們還需要知道三個節(jié)點.

這么多，只需轉(zhuǎn)到代碼.

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ù)，反向后的返回值是反向后單鏈表的頭節(jié)點.

最好自己在IDE中將其敲響，以加深您的印象.

單鏈表反轉(zhuǎn)也可以通過遞歸來實現(xiàn)，但是不建議在這里使用，每個人都知道.

遞歸仍然使用函數(shù)調(diào)用棧的思想鏈表反轉(zhuǎn) java，實際上實際上是一個棧. 沒什么可說的，直接進(jìn)入代碼即可.

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;
}

這時，已經(jīng)介紹了單鏈接列表反轉(zhuǎn)的內(nèi)容. 學(xué)習(xí)算法仍然需要考慮編寫更多內(nèi)容并進(jìn)行練習(xí). 建議您在IDE中手動將其敲門以加深印象.

本文來自本站，轉(zhuǎn)載請注明本文網(wǎng)址：
http://www.pc-fly.com/a/jisuanjixue/article-248104-1.html