用個(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é)果丑掺；(例1分析)
- 返回的是最后一步回溯的結(jié)果。
- 這里舉例說(shuō)明逃糟，看代碼：
public int testI(int i, boolean flag) {
if(i >= 5) return i;
System.out.print(i);
if (flag) {
return testI(++i, true);
} else {
testI(++i, false);
return i;
}
}
- 當(dāng)調(diào)用函數(shù)的flag為false吼鱼，代碼簡(jiǎn)化成
public int testI(int i, boolean flag) {
if(i >= 5) return i;
System.out.print(i);
testI(++i, false);
return i;
}
// 012341
此時(shí)對(duì)應(yīng)第一步情況，因?yàn)樽詈笫莚eturn一個(gè)顯式的值绰咽，那么向下遞歸后菇肃，得到了結(jié)果只被上一層遞歸得到，最終返回的結(jié)果就是第一層取募。
- 當(dāng)調(diào)用函數(shù)的flag為true琐谤，代碼簡(jiǎn)化成
public int testI(int i, boolean flag) {
if(i >= 5) return i;
System.out.print(i);
return testI(++i, true);
}
// 012345
對(duì)應(yīng)最后一步情況，每次返回的是testI函數(shù)本身的值玩敏，最終層的結(jié)果斗忌，被回溯上去质礼，得到的結(jié)果是最終層。
那么這兩種情況如何判斷呢织阳？
看最終return與下一層有沒(méi)有關(guān)系眶蕉。
- 第一種，只是用到了下層唧躲，但下層和返回結(jié)果沒(méi)有直接關(guān)系（即返回的值或引用沒(méi)有與下級(jí)產(chǎn)生直接關(guān)系）造挽，則為第一種情況。
- 若有關(guān)系（最常見(jiàn)的就是return 遞歸函數(shù)return testI()）弄痹，那么返回值就是終結(jié)遞歸的那一條語(yǔ)句（if(i >= 5) return i）饭入。
現(xiàn)在再來(lái)看這個(gè)題目。
因?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)建返回條件
if (head == null || head.next == null) return head;
- 對(duì)當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)進(jìn)行值的判斷饭耳，若相等，則刪除該節(jié)點(diǎn)执解，并查看下一個(gè)節(jié)點(diǎn)，直到值不相等纲酗。
if (head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next; // 迭代找到下一層的節(jié)點(diǎn)
}
// 返回下一層回溯上來(lái)的節(jié)點(diǎn)
return deleteDuplicates1(head.next);
}
- 若不相等衰腌，需要保留當(dāng)前節(jié)點(diǎn)，并將下一層的節(jié)點(diǎn)接在后面觅赊。返回的是當(dāng)前節(jié)點(diǎn)右蕊。
else {
// 接下一層的節(jié)點(diǎn)
head.next = deleteDuplicates(head.next);
return head;
}
- 若想要?jiǎng)h除重復(fù)節(jié)點(diǎn)，但只是刪除到只剩一個(gè)吮螺。怎么辦呢饶囚？顯然從第二步的返回值下手，不能直接返回回溯上來(lái)的節(jié)點(diǎn)鸠补，而要拼接一下萝风。
head.next = deleteDuplicates1(head.next);
return head;
