链表的算法，递归是一个很常见的结题思路，但很容易陷入套娃中，特别是带返回值的递归，有时候就很懵，不知道到底返回了什么。这里做了个简单的思考，有所感悟，记一下。
用一个题目举例子：
一条非递减的链表，请删除链表中带重复值的节点，只保留删减前不重复的节点，返回头结点。
如[1 - 2 - 2 - 3] => [1 - 3]
思路
递归的实质就是: 向下遍历, 然后向上回溯. 核心是: 只看当前层. 带返回值的递归, 返回值有两种可能:
- 返回的是第一层的返回结果
- 返回的是最后一层的结果
这里举例说明, 看代码
当调用函数的flag为false, 代码为
当调用函数的flag为true, 代码化简成
那么这两种情况如何判断呢?
- 看最终return与下层有没有关系
- 第一种: 只用到了下层, 但下层和返回结果没有直接关系(即返回的值或引用没有与下级产生直接关系),
- 若有关系(最常见的是return 递归函数名), 那么返回值就是终结递归的那一条语句返回的值(if(i>=5) return i;)
现在再来看题目
因为要返回链表头结点head, 显然是要用第一种方法, 最终返回的第一层就是真实的头结点
那么每一层要做的事情就是: 判断当前层有没有相同的多个节点
- 若有: 将当前层所有相同节点全部删掉, 并返回下一层回溯上来的结果(因为复数个节点要全部删掉)
-
若没有：保留当前节点并返回给上一层
-
先构建返回条件
-
对当前节点和下一个节点进行值的判断, 若相等, 则删除该节点, 并查看下一个节点, 直到值不相等
- 若不相等, 则需要保留当前节点, 并将下一层节点接在后面. 返回的是当前的节点
4.若想要删除重复节点, 但只删除到剩下一个, 而不是全部删除, 怎么办呢? 显然从第二步的返回值开始下手, 不能直接返回回溯上来的节点. 而是要拼接一下再返回.
image.png
