大家好，我是王有志，欢迎和我聊技术，聊漂泊在外的生活。快来加入我们的Java提桶跑路群：共同富裕的Java人。
在数据结构：链表中，我们实现了链表的删除方法，但代码看起来并不“优雅”，那么今天我们就来尝试使用多种方法，“优雅”的实现链表的删除方法。
移除链表元素
今天我们从一道练习题开始：203.移除链表元素。为了方便我们把力扣提供的节点声明抄过来：
public class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
题目中给定了这样的一个头节点head和待删除元素val，要求删除链表中对应的元素。
“朴素”的删除方式
这道题目很简单，甚至是比数据结构：链表中实现的删除方法还要简单，因为我们不需要维护头节点，尾节点以及链表的规模。
照葫芦画瓢可以得到如下代码：
public static ListNode removeElements(ListNode head, int val) {
while (head != null && head.val == val) {
ListNode next = head.next;
head.next = null;
head = next;
}
if (head == null) {
return null;
}
ListNode prev = head;
while (prev.next != null) {
ListNode current = prev.next;
if (current.val == val) {
prev.next = current.next;
current = null;
} else {
prev = prev.next;
}
}
return head;
}
空间换“美感”
虽然“朴素”的方法在功能上是没有问题的，但是过多的if语句很让头疼，我们是不是可以减少if语句，使用统一的逻辑去处理呢？
很容易想到的是，我们可以创建新的链表，去承载不需要删除的元素。接下来，我们使用移除链表元素题目中的示例一来描述：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
代码如下：
public static ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
ListNode newHead = null;
ListNode current = null;
while (head != null) {
if (head.val != val) {
if (newHead == null) {
newHead = new ListNode(head.val);
current = newHead;
} else {
current.next = new ListNode(head.val);
current = current.next;
}
}
head = head.next;
}
return newHead;
}
虽然代码只少了1行，但是逻辑却简单了起来，仅仅只需要一个while循环，也只需要处理一次头节点的逻辑即可。
你有没有发现，上面的两种方法，都要对头节点进行特殊处理，是不是“消除”了头节点逻辑会更加简单？
那么我们可以添加一个“有名无实”的头节点，让真实的头节点退下来，这样就可以使用统一的逻辑的处理，代码如下：
public static ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
ListNode virtualHead = new ListNode();
ListNode prev = virtualHead;
while (head != null) {
if (head.val != val) {
prev.next = new ListNode(head.val);
prev = prev.next;
}
head = head.next;
}
return virtualHead.next;
}
这样仅代码少了很多，而且代码的逻辑也变得十分清晰了，我们习惯将这种“假的”头节点称为虚拟头节点。
虚拟头节点
虚拟头节点是解决链表问题中非常好用的方法，链表中的多种操作都要对头节点进行特殊逻辑处理，这样既不美观，也容易遗漏边界情况，如果没有头节点，处理起来是不是就非常容易了？
在王争老师的《数据结构与算法之美》中，也提到了这种方法，他称虚拟头节点为“哨兵”，并将含有“哨兵”的链表称为“带头链表”，当然无论叫什么，其实现思想都是相同的。
上面的实现的删除操作中，我们讨了一个巧，在没有要求空间复杂度的情况下，我们从删除变成了“新增”，空间复杂度是$O(n)$，如果我们要求空间复杂度为$O(1)$呢？
private static ListNode removeElements(ListNode head, int val) {
ListNode virtualHead = new ListNode();
virtualHead.next = head;
ListNode prev = virtualHead;
while (prev.next != null) {
ListNode current = prev.next;
if (current.val == val) {
prev.next = current.next;
current.next = null;
} else {
prev = prev.next;
}
}
return virtualHead.next;
}
递归-优雅永不过时
我们通过虚拟头节点，成功实现了移除头节点的特殊逻辑，减少了代码量，使得结构更加清晰，不过有没有更加“优雅”的解法？
显然是有的，还记得我们在[[04.编程技巧：从斐波那契数列到递归]]中引用邓俊峰老师的话吗？其中有一句：
从程序结构的角度看，递归模式能够统筹纷繁多变的具体情况，避免复杂的分支以及嵌套的循环，从而更为简明地描述和实现算法，减少代码量，提高算法的可读性，保证算法的整体效率。
另外我们也提到了，递归是将复杂庞大的问题不断的拆分成更小的问题，逐一解决后合并结果。拆分的动作是递，合并的动作是归，结合起来便是递归。
在这道题目中我们如何去拆分问题？可以将链表拆分成子链表，再进行逻辑处理：
这就是我们拆分链表的过程，也是递归中最重要的部分，将大规模问题拆分成基础问题。
在这道题目中，最基础的问题是什么？是链表中的节点是否符合删除的要求，那么求解就非常简单了：
private static ListNode removeElements(ListNode node, int val) {
if(node.val == val) {
return node.next;
}else {
return node;
}
}
好了，我们有了拆分的过程，也对基础问题进行了求解，最后只需要合并问题的结果了，合并的过程也很简单。
每次都会从输入链表中拆分出子链表，合并时，只需要将处理过后的子链表作为上一次调用的后继节点即可，代码如下：
prevNode.next = removeElements(prevNode.next, val);
这样我们再处理下边界情况，将两部分结合起来，就可以写出完整的代码了：
private static ListNode removeElements(ListNode head, int val) {
if(head == null) {
return null;
}
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
我们再来分析下递归的复杂度，时间复杂度$O(n)$是一定的了，链表的特性就决定了牵扯到查找，时间复杂度就一定为$O(n)$，那么空间复杂度呢？
从纸面上看，没有引入任何临时变量，不需要额外的空间，堪称完美。但是不要忘记递归是方法调用，那么就需要调用栈，隐性的开销还是会比较大。
再谈递归
说真的，第一次见到递归解法时，我是一头雾水。直到动手画出递和归的过程，才理解递归的解法多么巧妙，不禁感叹前人的智慧。
这也让我想起来Aditya Bhargava在《算法图解》中说到的：
递归是我最喜欢的主题之一，它将人分成三个截然不同的阵营：恨它的、爱它的以及恨了几年后又爱上它的。
现在，我想我是爱上递归了。
言归正传，我们来总结下实现递归都需要哪些要素：
问题可以拆分为规模更小的基础问题；
基础问题的解法与原始问题一致；
递归存在出口条件。
而递归的过程也可以拆分为3个阶段：
不断拆分问题，就是递的过程；
解决基础问题；
合并问题的解，这是归的过程。
虽然递归实现了“终极优雅”，但在使用过程中还是要注意两个问题：重复计算和调用栈的消耗。
结语
今天我们对单向链表的删除方法不断的优化，减少复杂逻辑，减少代码量。
介绍了使用虚拟头节点处理链表中的问题，成功的消除了特殊逻辑，然后是通过递归，实现了“终极优雅”。
最后，我们第二次聊到了递归，当然这不会是我们最后一次聊递归，在后面树的内容中，递归会更加频繁的出现。
练习
本篇内容的代码仓库：Gitee代码仓库
好了，今天就到这里了，Bye~~
