題: 如圖1所示的鏈表結(jié)構(gòu), 寫(xiě)一個(gè)方法, 使用傳入的節(jié)點(diǎn)將該鏈表反轉(zhuǎn) (傳入的節(jié)點(diǎn)是首節(jié)點(diǎn), 返回的節(jié)點(diǎn)是反轉(zhuǎn)之后新的首節(jié)點(diǎn))
解析:? 反轉(zhuǎn)鏈表的最終結(jié)果, 肯定是 5 -- 4 -- 3 -- 2 -- 1. 按照這個(gè)順序, 我們可以這么想: 我們需要返回一個(gè)新的首節(jié)點(diǎn)(newHead), 那么不妨聲明一個(gè)要返回的節(jié)點(diǎn)變量, 然后進(jìn)行反轉(zhuǎn)操作, 再將這個(gè)新的節(jié)點(diǎn)(newHead)返回回去, 就可以了.
但是反轉(zhuǎn)的過(guò)程應(yīng)該怎么做呢?
在這個(gè)題目中, 我們需要的結(jié)果是, newHead指向5, 5指向4, ... 直到1指向null. 但是我們所知道的, 也就是一個(gè)oldHead, 所以我們只能從oldHead出發(fā), 依次拿到每一個(gè)節(jié)點(diǎn)指向的節(jié)點(diǎn), 然后再串起來(lái),
也就是說(shuō), 我們可以通過(guò)oldHead這個(gè)節(jié)點(diǎn), 依次拿到它后面的所有節(jié)點(diǎn), 然后在每一次拿到這個(gè)節(jié)點(diǎn)時(shí), 將這個(gè)節(jié)點(diǎn)直接插入在newHead的后面, 同時(shí), 將oldHead的next, 指向被拿走的這個(gè)節(jié)點(diǎn)的next.?
具體步驟如下:
第一步: 讓newHead指向節(jié)點(diǎn)1, oldHead指向節(jié)點(diǎn)1的next, 節(jié)點(diǎn)1的next指向null. 因?yàn)榉崔D(zhuǎn)之后, 節(jié)點(diǎn)1是最后一個(gè)了, 它的next就是null. 變成了圖2-1.
第二步: 在完成第一步后, oldHead這個(gè)節(jié)點(diǎn)就成了節(jié)點(diǎn)2. 此時(shí)讓oldHead指向節(jié)點(diǎn)2的next也就是節(jié)點(diǎn)3, 讓newHead指向節(jié)點(diǎn)2, 節(jié)點(diǎn)2的next再去指向節(jié)點(diǎn)1, 就變成了圖2-2
第三步: 重復(fù)這個(gè)交換步驟, 直到最后oldHead指向了null, 那么鏈表所有的節(jié)點(diǎn)都交換完了, 也就是反轉(zhuǎn)完了, 變成了圖2-3
到此為止, 鏈表就反轉(zhuǎn)完成
具體代碼如下:
但是在整個(gè)交換流程中, 如果我們不使用一個(gè)臨時(shí)變量去接收oldHead要指向的那個(gè)節(jié)點(diǎn), 當(dāng)我們改動(dòng)了oldHead之后, 那個(gè)節(jié)點(diǎn)對(duì)于的線就斷掉了, 從該節(jié)點(diǎn)以后的所有節(jié)點(diǎn), 都會(huì)釋放了.?
?循環(huán)到最后, oldHead指向了null, 結(jié)束. 鏈表成功反轉(zhuǎn), 新的首節(jié)點(diǎn)就是這個(gè)newHead.
