优雅的删除链表元

封面：优雅的删除链表元素.png

王有志，一个分享硬核Java技术的互金摸鱼侠
加入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]

图1：空间换“美感”.png
代码如下：

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;
}

这样仅代码少了很多，而且代码的逻辑也变得十分清晰了，我们习惯将这种“假的”头节点称为虚拟头节点。

虚拟头节点

虚拟头节点是解决链表问题中非常好用的方法，链表中的多种操作都要对头节点进行特殊逻辑处理，这样既不美观，也容易遗漏边界情况，如果没有头节点，处理起来是不是就非常容易了？
图2：虚拟头节点.png
在王争老师的《数据结构与算法之美》中，也提到了这种方法，他称虚拟头节点为“哨兵”，并将含有“哨兵”的链表称为“带头链表”，当然无论叫什么，其实现思想都是相同的。
上面的实现的删除操作中，我们讨了一个巧，在没有要求空间复杂度的情况下，我们从删除变成了“新增”，空间复杂度是 $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.编程技巧：从斐波那契数列到递归]]中引用邓俊峰老师的话吗？其中有一句：

从程序结构的角度看，递归模式能够统筹纷繁多变的具体情况，避免复杂的分支以及嵌套的循环，从而更为简明地描述和实现算法，减少代码量，提高算法的可读性，保证算法的整体效率。

另外我们也提到了，递归是将复杂庞大的问题不断的拆分成更小的问题，逐一解决后合并结果。拆分的动作是递，合并的动作是归，结合起来便是递归。
在这道题目中我们如何去拆分问题？可以将链表拆分成子链表，再进行逻辑处理：
图3：递归拆分链表.png
这就是我们拆分链表的过程，也是递归中最重要的部分，将大规模问题拆分成基础问题。
在这道题目中，最基础的问题是什么？是链表中的节点是否符合删除的要求，那么求解就非常简单了：

private static ListNode removeElements(ListNode node, int val) {
	if(node.val == val) {
		return node.next;
	}else {
		return node;
	}
}

好了，我们有了拆分的过程，也对基础问题进行了求解，最后只需要合并问题的结果了，合并的过程也很简单。
图4：递归合并链表.png
每次都会从输入链表中拆分出子链表，合并时，只需要将处理过后的子链表作为上一次调用的后继节点即可，代码如下：

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;
}