【日拱一卒】鏈表——鏈表反轉(遞歸解法)
前言
上篇我們主要介紹鏈表反轉的原地反轉解法。
除此以外,是否還有其他解法?
當然,今天就來看看鏈表反轉的遞歸解法。
遞歸
遞歸,字面意思,有”遞“也有”歸“
拿我們經常聽到的斐波那契數列來說,公式如下
f(n) = f(n-1) + f(n-2); f(1) = 1, f(2) = 1
現在比如求解f(5)的值,按照公式,可以展開爲f(5) = f(4) + f(3),如下圖所示
這時候,我們不知道f(3)和f(4)的值,沒關係,繼續展開,如下圖所示
從圖中可以看出,各個節點已經分解到不能再分解,此時的葉子節點都是已知值,f(1)=1,f(2)=2
”遞“過程走完了,下面開始”歸“
如上圖所示,沿着紅色箭頭的方向開始迴歸,最終得到f(5)的值爲8
如上就是遞歸的過程,從下面的代碼層面,我們可以看到底層的表示形式就是自己調用自己,直到滿足閾值條件則停止。
遞歸反轉鏈表
先上代碼
func reverse(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } newHead := reverse(head.Next) head.Next.Next = head head.Next = nil return newHead }
結合下圖
我們假設此時傳入的head指向的是帶反轉的鏈表,目前head的值爲5。
既然這裏用到了遞歸的思想,那麼這裏
newHead := reverse(head.Next)
head.Next即爲4,我們拿到的newHead此時就是一個已經完成反轉的鏈表了,這是目前還差5這個節點。
下面只要將4指向5,再讓5的Next指向nil,就是一個完整的反轉鏈表了。
head.Next.Next = head即表示4指向5(head.Next爲4,head爲5)
head.Next = nil(5的下一個節點即head.Next)
5和4的關係是這樣,以此類推,4和3,3和2,2和1都是這樣遞歸來的。
這裏是比較繞,大概明白這個思想吧。
不忘初心
老王:你不好好種地,你以後長大能幹什麼
小王:學算法
老王:學算法?!你數組、鏈表、棧、隊列、堆、排序、查找都整不明白,你學什麼算法
小王:我只學鏈表反轉遞歸解法
老王:。。。
如果您覺得閱讀本文對您有幫助,請點一下“ 推薦 ”按鈕,您的 “推薦” 將是我最大的寫作動力!如果您想持續關注我的文章,請掃描二維碼,關注JackieZheng的微信公衆號,我會將我的文章推送給您,並和您一起分享我日常閱讀過的優質文章。
<em><img src="https://images0.cnblogs.com/blog2015/619240/201505/162205410643708.jpg" alt="" /></em>