資訊專欄INFORMATION COLUMN
摘要：扯淡之前聽(tīng)說(shuō)過(guò)面試反轉(zhuǎn)鏈表的梗，也嘗試著自己實(shí)現(xiàn)了一次，算是比較簡(jiǎn)單的問(wèn)題。當(dāng)然，前提是我們只持有頭節(jié)點(diǎn)的引用，且稱為，那么鏈表反轉(zhuǎn)后的頭節(jié)點(diǎn)，就是。
扯淡
之前聽(tīng)說(shuō)過(guò)google面試反轉(zhuǎn)鏈表的梗，也嘗試著自己實(shí)現(xiàn)了一次，算是比較簡(jiǎn)單的問(wèn)題。但在紙上手寫(xiě)代碼的時(shí)候，思維就很亂，可能是隔的時(shí)間長(zhǎng)忘記了，或者之前就跟本沒(méi)有理清思路，所以被虐的很慘。
這篇文章的目的就是梳理一下思路，加深印象。如果有更好的算法，留言求虐啊～
這是一個(gè)普通的鏈表，由ABCD4個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)都包含數(shù)據(jù)區(qū)-data和指向下一個(gè)節(jié)點(diǎn)的引用-next
反轉(zhuǎn)鏈表，顧名思義就是將鏈表每個(gè)節(jié)點(diǎn)的next引用反過(guò)來(lái)，如ABCD，變?yōu)镈CBA。當(dāng)然，前提是我們只持有頭節(jié)點(diǎn)的引用，且稱為Node a，那么鏈表反轉(zhuǎn)后的頭節(jié)點(diǎn)，就是Node d。
分析要將此鏈表反轉(zhuǎn)，我們核心的需求是：修改每一個(gè)節(jié)點(diǎn)的next引用，將next指向前一個(gè)節(jié)點(diǎn)，將原來(lái)的頭節(jié)點(diǎn)A中的next，指向null。
既然每一個(gè)節(jié)點(diǎn)都需要操作，那就考慮循環(huán)吧，設(shè)一個(gè)索引（或者稱為游標(biāo)）node（可以利用節(jié)點(diǎn)A的引用），從節(jié)點(diǎn)A跑到節(jié)點(diǎn)D，當(dāng)它再往后移動(dòng)指向null時(shí)，循環(huán)結(jié)束。那么循環(huán)邊界條件則為
while(node != null){
//do something
}
然后我們?cè)倏纯疵總€(gè)節(jié)點(diǎn)做一次反轉(zhuǎn)（即每次循環(huán)），都需要做什么事情
在修改當(dāng)前節(jié)點(diǎn)的next引用之前，要先保存其值，為了避免丟失下一個(gè)節(jié)點(diǎn)（即Node next）的引用。
進(jìn)行反轉(zhuǎn)，修改當(dāng)前節(jié)點(diǎn)的next，使之指向上一個(gè)節(jié)點(diǎn)（即Node last）
要保存當(dāng)前節(jié)點(diǎn)的引用，為了提供給下一次循環(huán)時(shí)，對(duì)下個(gè)節(jié)點(diǎn)進(jìn)行反轉(zhuǎn)
為了保證while循環(huán)可以從頭節(jié)點(diǎn)A遍歷到尾節(jié)點(diǎn)D，那么游標(biāo)node在循環(huán)體最后要向后移動(dòng)一個(gè)節(jié)點(diǎn)，即指向下一個(gè)節(jié)點(diǎn)。
代碼Node reversalLinkedList(Node node){
Node last = null;
Node next = null;
while(node != null){
next = node.getNext();//1 拿到下個(gè)節(jié)點(diǎn)的引用，為了提供給第4步使node向鏈表后方移動(dòng)
node.setNext(last);//2 將當(dāng)前節(jié)點(diǎn)指向上一個(gè)節(jié)點(diǎn)
last = node;//3 將last指向當(dāng)前節(jié)點(diǎn)，提供給下次循環(huán)的第2步
node = next;//4 將當(dāng)前節(jié)點(diǎn)的引用（即游標(biāo)）指向下一個(gè)節(jié)點(diǎn)
}
/*
* 循環(huán)完成后，node和next都指向了原節(jié)點(diǎn)D的next指向的位置，即null
* 而last指向了上述null前面的位置，即節(jié)點(diǎn)D
* 將last返回，則得到鏈表ABCD反轉(zhuǎn)后鏈表DCBA的頭節(jié)點(diǎn)D
*/
return last;
}
邏輯其實(shí)很簡(jiǎn)單，需要注意的就是每次循環(huán)時(shí)需要暫存的引用 -- next,last
圖解每次循環(huán)其實(shí)就是修改當(dāng)前節(jié)點(diǎn)next的引用+三個(gè)引用(last,node,next)的后移，如下圖
第一次循環(huán)前
第一次循環(huán)的過(guò)程
第一次循環(huán)結(jié)束后
最后全部反轉(zhuǎn)后
保存當(dāng)前節(jié)點(diǎn)，上一個(gè)節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)的引用
每次循環(huán)最后，當(dāng)前節(jié)點(diǎn)向后移動(dòng)
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65550.html
摘要：假設(shè)反轉(zhuǎn)對(duì)象節(jié)點(diǎn)為，反轉(zhuǎn)指向的結(jié)點(diǎn)為，反轉(zhuǎn)后指向的結(jié)點(diǎn)為首結(jié)點(diǎn)。當(dāng)然也可以根據(jù)棧先進(jìn)后出的特點(diǎn)，使用棧反轉(zhuǎn)鏈表。 ??前面的話?? 大家好！博主開(kāi)辟了一個(gè)新的專欄—...
摘要：算法思路兩種方法一般反轉(zhuǎn)遞歸法一般解決定義三個(gè)指針，分別為，存儲(chǔ)當(dāng)前結(jié)點(diǎn)，指向反轉(zhuǎn)好的結(jié)點(diǎn)的頭結(jié)點(diǎn)，存儲(chǔ)下一結(jié)點(diǎn)信息。遞歸法重點(diǎn)分析先確定終止條件當(dāng)下一結(jié)點(diǎn)為時(shí)，返回當(dāng)前節(jié)點(diǎn)判斷當(dāng)前的鏈表是否為遞歸找到尾結(jié)點(diǎn)，將其存儲(chǔ)為頭結(jié)點(diǎn)。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿 題目：Reverse...
摘要：今天來(lái)將一下面試中經(jīng)常問(wèn)到的一個(gè)問(wèn)題鏈表反轉(zhuǎn)。題目給一個(gè)單向鏈表，請(qǐng)編寫(xiě)一個(gè)函數(shù)，把鏈表反轉(zhuǎn)，并把反轉(zhuǎn)的鏈表返回。假設(shè)給的節(jié)點(diǎn)為雙向鏈表反轉(zhuǎn)函數(shù)如下 今天來(lái)將一下面試中經(jīng)常問(wèn)到的一個(gè)問(wèn)題：鏈表反轉(zhuǎn)。 【題目1】給一個(gè)單向鏈表，請(qǐng)編寫(xiě)一個(gè)函數(shù)，把鏈表反轉(zhuǎn)，并把反轉(zhuǎn)的鏈表返回。 假設(shè)給的節(jié)點(diǎn)為 class ListNode{ int val; ListNode next; ...
摘要：示例輸入輸出進(jìn)階你可以迭代或遞歸地反轉(zhuǎn)鏈表?？梢栽O(shè)置一個(gè)指針，指向，保證后續(xù)的操作然后將，往前挪動(dòng)，當(dāng)然還有，直到為空，這時(shí)指向反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)。接下來(lái)考慮遞歸結(jié)束的條件非常顯然，子鏈表只有一個(gè)節(jié)點(diǎn)是遞歸結(jié)束，直接返回該節(jié)點(diǎn)。 本文來(lái)自 SoulOH 的CSDN 博客 ，原文地址請(qǐng)點(diǎn)擊：https://blog.csdn.net/SoulOH/... 題目:反轉(zhuǎn)一個(gè)單鏈表。 示例: ...
閱讀 4817·2021-11-18 13:23
閱讀 927·2021-09-22 15:24
閱讀 1953·2021-09-06 15:00
閱讀 2660·2021-09-03 10:30
閱讀 1314·2021-09-02 15:15
閱讀 2112·2019-08-30 15:54
閱讀 3057·2019-08-30 15:44
閱讀 1480·2019-08-29 15:12
