鏈表的算法掸宛，遞歸是一個(gè)很常見(jiàn)的結(jié)題思路死陆，但很容易陷入套娃中，特別是帶返回值的遞歸唧瘾，有時(shí)候就很懵措译，不知道到底返回了什么。這里做了個(gè)簡(jiǎn)單的思考饰序，有所感悟领虹，記一下。
用一個(gè)題目舉例子：
一條非遞減的鏈表求豫，請(qǐng)刪除鏈表中帶重復(fù)值的節(jié)點(diǎn)塌衰，只保留刪減前不重復(fù)的節(jié)點(diǎn)诉稍，返回頭結(jié)點(diǎn)。
如[1 - 2 - 2 - 3] => [1 - 3]
思路
遞歸的實(shí)質(zhì)就是: 向下遍歷, 然后向上回溯. 核心是: 只看當(dāng)前層. 帶返回值的遞歸, 返回值有兩種可能:
- 返回的是第一層的返回結(jié)果
- 返回的是最后一層的結(jié)果
這里舉例說(shuō)明, 看代碼
當(dāng)調(diào)用函數(shù)的flag為false, 代碼為
當(dāng)調(diào)用函數(shù)的flag為true, 代碼化簡(jiǎn)成
那么這兩種情況如何判斷呢?
- 看最終return與下層有沒(méi)有關(guān)系
- 第一種: 只用到了下層, 但下層和返回結(jié)果沒(méi)有直接關(guān)系(即返回的值或引用沒(méi)有與下級(jí)產(chǎn)生直接關(guān)系),
- 若有關(guān)系(最常見(jiàn)的是return 遞歸函數(shù)名), 那么返回值就是終結(jié)遞歸的那一條語(yǔ)句返回的值(if(i>=5) return i;)
現(xiàn)在再來(lái)看題目
因?yàn)橐祷劓湵眍^結(jié)點(diǎn)head, 顯然是要用第一種方法, 最終返回的第一層就是真實(shí)的頭結(jié)點(diǎn)
那么每一層要做的事情就是: 判斷當(dāng)前層有沒(méi)有相同的多個(gè)節(jié)點(diǎn)
- 若有: 將當(dāng)前層所有相同節(jié)點(diǎn)全部刪掉, 并返回下一層回溯上來(lái)的結(jié)果(因?yàn)閺?fù)數(shù)個(gè)節(jié)點(diǎn)要全部刪掉)
-
若沒(méi)有：保留當(dāng)前節(jié)點(diǎn)并返回給上一層
-
先構(gòu)建返回條件
-
對(duì)當(dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)進(jìn)行值的判斷, 若相等, 則刪除該節(jié)點(diǎn), 并查看下一個(gè)節(jié)點(diǎn), 直到值不相等
- 若不相等, 則需要保留當(dāng)前節(jié)點(diǎn), 并將下一層節(jié)點(diǎn)接在后面. 返回的是當(dāng)前的節(jié)點(diǎn)
4.若想要?jiǎng)h除重復(fù)節(jié)點(diǎn), 但只刪除到剩下一個(gè), 而不是全部刪除, 怎么辦呢? 顯然從第二步的返回值開(kāi)始下手, 不能直接返回回溯上來(lái)的節(jié)點(diǎn). 而是要拼接一下再返回.
image.png
