09.数据结构：优雅的删除链表元素

大家好，我是王有志。

在08.数据结构：第一个动态结构-链表中，我们实现了链表的删除方法，但代码看起来并不“优雅”，那么今天我们就来尝试使用多种方法，“优雅”的实现链表的删除方法。

移除链表元素

今天我们从一道练习题开始：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，要求删除链表中对应的元素。

“朴素”的删除方式

这道题目很简单，甚至是比08.数据结构：第一个动态结构-链表中实现的删除方法还要简单，因为我们不需要维护头节点，尾节点以及链表的规模。

照葫芦画瓢可以得到如下代码：

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语句，使用统一的逻辑去处理呢？

很容易想到的是，我们可以创建新的链表，去承载不需要删除的元素。接下来，我们使用203.移除链表元素题目中的示例一来描述：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

空间换“美感”.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;
}

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

虚拟头节点

虚拟头节点是解决链表问题中非常好用的方法，链表中的多种操作都要对头节点进行特殊逻辑处理，这样既不美观，也容易遗漏边界情况，如果没有头节点，处理起来是不是就非常容易了？

虚拟头节点.png

在王争老师的《数据结构与算法之美》中，也提到了这种方法，他称虚拟头节点为“哨兵”，并将含有“哨兵”的链表称为“带头链表”，当然无论叫什么，其实现思想都是相同的。

上面的实现的删除操作中，我们讨了一个巧，在没有要求空间复杂度的情况下，我们从删除变成了“新增”，空间复杂度是，如果我们要求空间复杂度为呢？

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.编程技巧：从斐波那契数列到递归
中引用邓俊峰老师的话吗？其中有一句：

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

另外我们也提到了，递归是将复杂庞大的问题不断的拆分成更小的问题，逐一解决后合并结果。拆分的动作是递，合并的动作是归，结合起来便是递归。

在这道题目中我们如何去拆分问题？可以将链表拆分成子链表，再进行逻辑处理：

递归拆分链表.png

这就是我们拆分链表的过程，也是递归中最重要的部分，将大规模问题拆分成基础问题。

在这道题目中，最基础的问题是什么？是链表中的节点是否符合删除的要求，那么求解就非常简单了：

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

好了，我们有了拆分的过程，也对基础问题进行了求解，最后只需要合并问题的结果了，合并的过程也很简单。

递归合并链表.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;
}

我们再来分析下递归的复杂度，时间复杂度是一定的了，链表的特性就决定了牵扯到查找，时间复杂度就一定为，那么空间复杂度呢？

从纸面上看，没有引入任何临时变量，不需要额外的空间，堪称完美。但是不要忘记递归是方法调用，那么就需要调用栈，隐性的开销还是会比较大。

再谈递归

说真的，第一次见到递归解法时，我是一头雾水。直到动手画出递和归的过程，才理解递归的解法多么巧妙，不禁感叹前人的智慧。

这也让我想起来Aditya Bhargava在《算法图解》中说到的：

递归是我最喜欢的主题之一，它将人分成三个截然不同的阵营：恨它的、爱它的以及恨了几年后又爱上它的。

现在，我想我是爱上递归了。

言归正传，我们来总结下实现递归都需要哪些要素：

• 问题可以拆分为规模更小的基础问题；
• 基础问题的解法与原始问题一致；
• 递归存在出口条件。

而递归的过程也可以拆分为3个阶段：

• 不断拆分问题，就是递的过程；
• 解决基础问题；
• 合并问题的解，这是归的过程。

虽然递归实现了“终极优雅”，但在使用过程中还是要注意两个问题：重复计算和调用栈的消耗。

结语

今天我们对单向链表的删除方法不断的优化，减少复杂逻辑，减少代码量。

介绍了使用虚拟头节点处理链表中的问题，成功的消除了特殊逻辑，然后是通过递归，实现了“终极优雅”。

最后，我们第二次聊到了递归，当然这不会是我们最后一次聊递归，在后面树的内容中，递归会更加频繁的出现。

练习

• 203.移除链表元素
• 234.回文链表
• 876.链表的中间结点
• 剑指 Offer 25.合并两个排序的链表
• 剑指 Offer 62.圆圈中最后剩下的数字

本篇内容的代码仓库：

• Gitee代码仓库
• Github代码仓库

---

好了，今天就到这里了，Bye~~