資訊專欄INFORMATION COLUMN
摘要：?jiǎn)栴}最近研究算法，遇到的一道很有意思的問題怎么把一個(gè)鏈表反轉(zhuǎn)很容易想到一個(gè)方法遍歷鏈表，數(shù)組作棧存儲(chǔ)路徑，元素逐個(gè)出棧得到的就是反轉(zhuǎn)后的鏈表查找資料發(fā)現(xiàn)，有更好的方式實(shí)現(xiàn)。老規(guī)矩，完整代碼見暗夜君王的練習(xí)鏈表反轉(zhuǎn)
問題
最近研究算法，遇到的一道很有意思的問題——怎么把一個(gè)鏈表反轉(zhuǎn)？
很容易想到一個(gè)方法：遍歷鏈表，數(shù)組作棧存儲(chǔ)路徑，元素逐個(gè)出棧得到的就是反轉(zhuǎn)后的鏈表！查找資料發(fā)現(xiàn)，有更好的方式實(shí)現(xiàn)。
仔細(xì)研究后，終于明白了其中的奧妙。小僧掌握了兩種方法，以下分別進(jìn)行說明。
首先給出鏈表結(jié)構(gòu)：
public class LinkedNode {
Integer id ;
LinkedNode next;
public LinkedNode(Integer id) {
this.id = id;
}
}
下一步構(gòu)造出上圖的鏈表結(jié)構(gòu)：
LinkedNode node1 = new LinkedNode(1); LinkedNode node2 = new LinkedNode(2); LinkedNode node3 = new LinkedNode(3); LinkedNode node4 = new LinkedNode(4); node1.next = node2; node2.next = node3; node3.next = node4;雙指針遍歷法
先給出代碼實(shí)現(xiàn)：
/**
* 鏈表翻轉(zhuǎn)，循環(huán) + 雙指針（pre、next）實(shí)現(xiàn)
* @param cur
* @return
*/
public LinkedNode reverse(LinkedNode cur){
LinkedNode pre = null;
while (cur!=null){
LinkedNode next = cur.next; // 1.
cur.next = pre; // 2.
pre = cur; // 3.
cur = next; // 4.
}
return pre;
}
循環(huán)體之前，鏈表示意圖：
之后進(jìn)入while循環(huán)，注釋標(biāo)注的四個(gè)步驟會(huì)產(chǎn)生如下變化（圖中編號(hào)與注釋編號(hào)一一對(duì)應(yīng)）：
第一次循環(huán)后，鏈表變成這樣：
之后的遍歷，鏈表的變化示意：
可見，while循環(huán)執(zhí)行完，pre指向的節(jié)點(diǎn)，已經(jīng)是最新的頭節(jié)點(diǎn)了！
遞歸法遞歸的實(shí)現(xiàn)方式，似乎更容易理解。
/**
* 鏈表反轉(zhuǎn)，遞歸實(shí)現(xiàn)
* @param node
* @return
*/
public LinkedNode reverse2(LinkedNode node){
if(node.next==null){
return node;
}
LinkedNode newHead = reverse2(node.next);
node.next.next = node; //node.next.next 換成 newHead.next 不行，因?yàn)閚ode在遞歸中在追溯上一個(gè)節(jié)點(diǎn)，仔細(xì)體會(huì)下
node.next = null;
return newHead;
}
首先會(huì)通過遞歸調(diào)用找到尾節(jié)點(diǎn)，之后做了兩件事：
尾節(jié)點(diǎn)反指 (node.next.next = node;)
當(dāng)前節(jié)點(diǎn)指向null節(jié)點(diǎn) (node.next = null;)
rentun newHead后，回溯到節(jié)點(diǎn)2（此時(shí)node就是節(jié)點(diǎn)2），再次重復(fù)之前的兩件事——節(jié)點(diǎn)反指和當(dāng)前節(jié)點(diǎn)指向null節(jié)點(diǎn)。
再次回溯，得到最終的結(jié)果。
老規(guī)矩，完整代碼見git：暗夜君王的demo練習(xí)——鏈表反轉(zhuǎn)
Done !
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/72714.html
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡(jiǎn)介：大家好，我是車神哥，府學(xué)路18號(hào)的車神? ?個(gè)人主頁：應(yīng)無所住而生...
摘要：第一遞歸函數(shù)功能假設(shè)的功能是求第項(xiàng)的值，代碼如下找出遞歸結(jié)束的條件顯然，當(dāng)或者我們可以輕易著知道結(jié)果。定義遞歸函數(shù)功能假設(shè)函數(shù)的功能是反轉(zhuǎn)但鏈表，其中表示鏈表的頭節(jié)點(diǎn)。可能很多人在大一的時(shí)候，就已經(jīng)接觸了遞歸了，不過，我敢保證很多人初學(xué)者剛開始接觸遞歸的時(shí)候，是一臉懵逼的，我當(dāng)初也是，給我的感覺就是，遞歸太神奇了！ 可能也有一大部分人知道遞歸，也能看的懂遞歸，但在實(shí)際做題過程中，卻不知道怎么...
摘要：先實(shí)現(xiàn)棧操作遍歷鏈表，把每個(gè)節(jié)點(diǎn)都進(jìn)中然后再遍歷鏈表，同時(shí)節(jié)點(diǎn)依次出棧，二者進(jìn)行比較。 ?作者簡(jiǎn)介：大家好，我是車神哥，府學(xué)路18號(hào)的車神? ?個(gè)人主頁：應(yīng)無...
閱讀 3669·2021-11-24 09:39
閱讀 1276·2021-09-30 09:48
閱讀 3259·2021-09-09 11:51
閱讀 2883·2021-09-08 10:41
閱讀 1329·2019-08-30 14:06
閱讀 2798·2019-08-30 14:01
閱讀 874·2019-08-29 17:11
閱讀 3169·2019-08-29 15:37
