递归删除链表中所有指定元素：为何最终结果不总是null？

这问题问得太戳痛点了！我当初刚啃递归操作链表的时候，也盯着这个逻辑愣了半天——明明递归到最后front（或者说head）都变成null了，怎么返回的结果不是全空呢？咱们拿实际代码和例子一步步掰明白。

先看一个最常见的递归实现（以Java为例）：

public ListNode removeElements(ListNode head, int val) {
    // 递归终止条件：当前节点为空，直接返回null
    if (head == null) {
        return null;
    }
    // 先递归处理当前节点的后续链表，把处理后的结果赋值给当前节点的next
    head.next = removeElements(head.next, val);
    // 判断当前节点要不要删：要删就返回处理后的next，不删就返回当前节点
    return head.val == val ? head.next : head;
}

核心误区：递归不是“一去不回”，回溯才是关键！ #

你觉得结果会是null，是只看到了递归向下深入的过程：从链表头一直调用到最后一个节点的next（也就是null），这时候触发终止条件返回null。但递归还有向上回溯的过程——每一层递归都会根据当前节点的情况，把合适的结果返回给上一层，相当于从链表尾部开始“重新拼接”一个符合要求的链表。

举个具体例子：假设链表是1 -> 2 -> 6 -> 3 -> 6，要删除值为6的节点，咱们走一遍完整流程：

1. 从head=1开始，调用removeElements(2,6)
2. 到head=2，调用removeElements(6,6)
3. 到head=6，调用removeElements(3,6)
4. 到head=3，调用removeElements(6,6)
5. 到head=6，调用removeElements(null,6)
6. 触发终止条件，返回null给上一层
7. 回到head=6这一层：把6.next设为null，然后判断6==6，所以返回6.next也就是null给上一层
8. 回到head=3这一层：把3.next设为null，判断3≠6，返回3给上一层
9. 回到head=6这一层：把6.next设为3，判断6==6，返回3给上一层
10. 回到head=2这一层：把2.next设为3，判断2≠6，返回2->3给上一层
11. 回到head=1这一层：把1.next设为2->3，判断1≠6，返回1->2->3——这就是最终结果！

关键总结 #

• 递归终止条件的return null只是处理“空链表”的边界情况，不是整个递归的最终返回值
• 每一层递归都会先把后续链表处理好，再决定当前节点是否要保留
• 回溯过程中，每一层都在给上一层传递“处理好的子链表头节点”，最终从最上层返回的就是整个处理后的链表头

内容的提问来源于stack exchange，提问作者dogkid45