需求
實(shí)現(xiàn)鏈表的反轉(zhuǎn)
輸入：1->2->3->4->5
輸出：5->4->3->2->1
難點(diǎn)
如果換成數(shù)據(jù)反轉(zhuǎn)疚脐，你會(huì)嗎（傻子才不會(huì)）璧榄。
按照常規(guī)思維，鏈表反轉(zhuǎn)需要知道最后一個(gè)元素革半，然后從最后一個(gè)元素依次往前找丛晦，直到遍歷到第一個(gè)元素即完成反轉(zhuǎn)。
但是這里并不是雙向鏈表涩馆，即使找到最后一個(gè)元素也找不到前繼節(jié)點(diǎn)行施。再者，即使是雙向鏈表魂那，通過(guò)找到尾結(jié)點(diǎn)再往回遍歷聽(tīng)著也不像是很高端的做法悲龟。
思路
除了找到尾結(jié)點(diǎn)進(jìn)行反轉(zhuǎn)的思路，我們是否可以考慮冰寻，在遍歷的同時(shí)就去做反轉(zhuǎn)的操作须教，類似
1->2->3->4->5
2->1->3->4->5
3->2->1->4->5
4->3->2->1->5
5->4->3->2->1
直覺(jué)告訴我們，肯定沒(méi)問(wèn)題斩芭，但是具體怎么做呢轻腺，看圖
第一步：畫出輸入鏈表結(jié)構(gòu)
第二步：初始化
注意
為了不干擾head指針，重新定義一個(gè)新的cur指針划乖，用于后面的遍歷贬养。pre指針表示最終反轉(zhuǎn)后的鏈表指針
指針存儲(chǔ)了指向變量的地址，比如這里的cur存儲(chǔ)的是head.next的地址
第三步：將1節(jié)點(diǎn)的next指向pre（即null）
注意
- 此時(shí)的pre指向的是一個(gè)null的地址琴庵，需要注意的是pre是一個(gè)指針误算，pre還可以指向其他節(jié)點(diǎn)（參見(jiàn)下一步操作）
第四步：將pre指向1節(jié)點(diǎn)
注意
- 將pre指向指向節(jié)點(diǎn)1，pre之前指向的是null迷殿，現(xiàn)在指向節(jié)點(diǎn)1儿礼，所以圖中虛線部分的連接就不存在了
- 這時(shí)候，我們成功的將第一個(gè)節(jié)點(diǎn)納入最終反轉(zhuǎn)鏈表pre中
第五步：解決指針丟失問(wèn)題
按照前面幾步的思路庆寺，我們依次遍歷后面的節(jié)點(diǎn)蚊夫，并對(duì)遍歷的節(jié)點(diǎn)做如上步驟的處理，這樣懦尝，最終我們就會(huì)得到反轉(zhuǎn)后的鏈表pre知纷。
但是，這里有個(gè)指針丟失的問(wèn)題陵霉。
原來(lái)cur指向節(jié)點(diǎn)1琅轧，cur.next指向節(jié)點(diǎn)2，但是在第三步的時(shí)候?qū)ur.next指向了null踊挠。所以使用cur.next就無(wú)法滿足我們遍歷節(jié)點(diǎn)2的需求了乍桂。
這時(shí)候，我們需要一個(gè)新指針，用來(lái)保證鏈表遍歷的時(shí)候不會(huì)斷掉模蜡，如下圖
注意
- 這里next指針需要在第二步初始化的時(shí)候就做好漠趁，不然這時(shí)候做next=cur.next就無(wú)法指向節(jié)點(diǎn)2了
第六步：開(kāi)啟下一次迭代
注意
- cur作為一個(gè)哨兵節(jié)點(diǎn)，指向節(jié)點(diǎn)2忍疾，開(kāi)始像處理節(jié)點(diǎn)1一樣處理節(jié)點(diǎn)2闯传，直到遍歷完所有節(jié)點(diǎn)
代碼實(shí)現(xiàn)
版本1
func reversrList(head *ListNode) *ListNode {
cur := head
var pre *ListNode = nil
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}
對(duì)照該代碼實(shí)現(xiàn)和上面幾個(gè)步驟，基本就可以摸透鏈表反轉(zhuǎn)的思路了卤妒。
這里還有一個(gè)更加簡(jiǎn)潔的代碼實(shí)現(xiàn)
版本2
func reversrList(head *ListNode) *ListNode {
cur := head
var pre *ListNode = nil
for cur != nil {
pre, cur, cur.Next = cur, cur.Next, pre
}
return pre
}
個(gè)人感覺(jué)不是很好理解甥绿，所以將其拆解成上面的代碼實(shí)現(xiàn)。
不忘初心
老王：你不好好種地则披，你以后長(zhǎng)大能干什么
小王：學(xué)算法
老王：學(xué)算法共缕？！你數(shù)組士复、鏈表图谷、棧、隊(duì)列阱洪、堆便贵、排序、查找都整不明白冗荸，你學(xué)什么算法
小王：我只學(xué)鏈表反轉(zhuǎn)
老王：承璃。。蚌本。
