【日拱一卒】鏈表——鏈表反轉
需求
實現鏈表的反轉
輸入：1->2->3->4->5
輸出：5->4->3->2->1
難點
如果換成數據反轉，你會嗎（傻子才不會）。
按照常規思維，鏈表反轉需要知道最後一個元素，然後從最後一個元素依次往前找，直到遍歷到第一個元素即完成反轉。
但是這裡並不是雙向鏈表，即使找到最後一個元素也找不到前繼節點。再者，即使是雙向鏈表，通過找到尾結點再往回遍歷聽著也不像是很高端的做法。
思路
除了找到尾結點進行反轉的思路，我們是否可以考慮，在遍歷的同時就去做反轉的操作，類似
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
直覺告訴我們，肯定沒問題，但是具體怎麼做呢，看圖
第一步：畫出輸入鏈表結構
第二步：初始化
注意
-
為了不干擾head指針，重新定義一個新的cur指針，用於後面的遍歷。pre指針表示最終反轉後的鏈表指針
-
指針存儲了指向變數的地址，比如這裡的cur存儲的是head.next的地址
第三步：將1節點的next指向pre（即null）
注意
- 此時的pre指向的是一個null的地址，需要注意的是pre是一個指針，pre還可以指向其他節點（參見下一步操作）
第四步：將pre指向1節點
注意
- 將pre指向指向節點1，pre之前指向的是null，現在指向節點1，所以圖中虛線部分的連接就不存在了
- 這時候，我們成功的將第一個節點納入最終反轉鏈表pre中
第五步：解決指針丟失問題
按照前面幾步的思路，我們依次遍歷後面的節點，並對遍歷的節點做如上步驟的處理，這樣，最終我們就會得到反轉後的鏈表pre。
但是，這裡有個指針丟失的問題。
原來cur指向節點1，cur.next指向節點2，但是在第三步的時候將cur.next指向了null。所以使用cur.next就無法滿足我們遍歷節點2的需求了。
這時候，我們需要一個新指針，用來保證鏈表遍歷的時候不會斷掉，如下圖
注意
- 這裡next指針需要在第二步初始化的時候就做好，不然這時候做next=cur.next就無法指向節點2了
第六步：開啟下一次迭代
注意
- cur作為一個哨兵節點，指向節點2，開始像處理節點1一樣處理節點2，直到遍歷完所有節點
程式碼實現
版本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
}
對照該程式碼實現和上面幾個步驟，基本就可以摸透鏈表反轉的思路了。
這裡還有一個更加簡潔的程式碼實現
版本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
}
個人感覺不是很好理解，所以將其拆解成上面的程式碼實現。
不忘初心
老王：你不好好種地，你以後長大能幹什麼
小王：學演算法
老王：學演算法？！你數組、鏈表、棧、隊列、堆、排序、查找都整不明白，你學什麼演算法
小王：我只學鏈表反轉
老王：。。。
如果您覺得閱讀本文對您有幫助，請點一下「推薦」按鈕，您的「推薦」將是我最大的寫作動力！如果您想持續關注我的文章，請掃描二維碼，關注JackieZheng的微信公眾號，我會將我的文章推送給您，並和您一起分享我日常閱讀過的優質文章。
