Swift 经典链表面试题：如何在不访问头节点的情况下删除指定节点？

摘要

在日常开发中，链表虽然不像数组、字典那么常用，但在某些场景下还是挺重要的。尤其是面试的时候，链表题目可是经典考点之一。今天我们要聊的就是一个看似简单，但很多人第一次做都会卡住的问题——删除单链表中的指定节点。

但这里有个限制条件——不能访问链表的头节点，这就让问题变得没那么简单了。我们要想办法直接操作给定的 node 来实现删除，而不能遍历链表去找到它的前驱节点。

接下来，我们会分析这个问题的痛点、找到最优解，并结合实际开发场景，看看它能在哪些地方派上用场。

痛点分析

1. 不能访问头节点，没法遍历

如果我们有 head，那这个问题就很简单了——遍历链表找到 node 的前一个节点 prev，然后 prev.next = node.next，删除搞定。
但现在问题是，我们连 head 都看不到，只能操作 node 本身。

2. 不能直接删除 node，但可以修改它

在 Swift 里，链表的节点是 class，是引用类型，意味着 node 本身只是个指针，删掉它不会改变链表结构。
但我们可以修改它的值，让它伪装成下一个节点，再让它跳过下一个节点，间接完成删除。

3. 不能删除最后一个节点

如果 node 是链表的最后一个元素，那我们就没法用这个方法了，因为它没有 next。
不过题目保证了 node 不是最后一个节点，所以这点不用担心。

问题描述

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

• 给定节点的值不应该存在于链表中。
• 链表中的节点数应该减少 1。
• node 前面的所有值顺序相同。
• node 后面的所有值顺序相同。

自定义测试：

• 对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
• 我们将构建链表，并将节点传递给你的函数。
• 输出将是调用你函数后的整个链表。

示例 1：

输入： head = [4,5,1,9], node = 5
输出： [4,1,9]
解释： 指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：

输入： head = [4,5,1,9], node = 1
输出： [4,5,9]
解释： 指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

提示：

• 链表中节点的数目范围是 [2, 1000]
• -1000 <= Node.val <= 1000
• 链表中每个节点的值都是 唯一 的
• 需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

题解思路

我们不能删除 node，但可以让它“变成”下一个节点。具体来说：

1. 把 node.next 的值赋给 node，让 node 变成 nextNode 的复制品。
2. 修改 node.next，让它指向 node.next.next，这样就跳过了原来的 nextNode，从链表中“移除”它。

代码实现（Swift）

class ListNode {
    var val: Int
    var next: ListNode?

    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func deleteNode(_ node: ListNode?) {
    guard let node = node, let nextNode = node.next else { return }
    
    node.val = nextNode.val // 把下一个节点的值复制到当前节点
    node.next = nextNode.next // 跳过下一个节点
}

代码解析

这个方法的核心在于：

• 不能真正删除 node，但可以把 node.next 的值拷贝过来，让 node “变身”。
• 然后让 node 指向 node.next.next，这样就绕开了 node.next，达到删除的效果。

举个例子：

• 原始链表：4 -> 5 -> 1 -> 9
• deleteNode(5) 后：
  • 5 变成 1
  • 5 的 next 指向 9
  • 结果：4 -> 1 -> 9

示例测试及结果

let head = ListNode(4)
let node2 = ListNode(5)
let node3 = ListNode(1)
let node4 = ListNode(9)

head.next = node2
node2.next = node3
node3.next = node4

deleteNode(node2) // 删除 5

最终链表变成：

4 -> 1 -> 9

时间复杂度

只修改了 node.val 和 node.next，都是 常数级操作，所以 时间复杂度是 O(1)。

空间复杂度

没使用额外的存储，空间复杂度是 O(1)。

这个技巧在实际开发中的应用

1. LRU 缓存

在实现 LRU（Least Recently Used）缓存 时，可能需要快速删除某个缓存项，而我们只能拿到这个节点本身。这个方法就可以直接移除它，而不影响整体结构。

2. 链表去重

有时候我们可能会在链表中删除重复的元素，比如给定 node 是重复值，我们可以用这个方法把它“跳过”。

3. 处理后台任务队列

假设我们有个任务队列，想要移除某个任务（节点），但我们没法获取整个队列的头部信息，这时候可以用这个方法来操作。

总结

• 这个问题的难点在于 不能访问 head，只能操作 node。
• 不能真正删除 node，但可以让它变成 next 的复制品，再跳过 next 节点。
• 代码实现简单，时间复杂度 O(1)，空间复杂度 O(1)，效率很高。
• 可以应用到 LRU 缓存、链表去重、任务队列等场景。

这个方法虽然有点“投机取巧”的感觉，但确实是一种高效的解决方案。希望这篇文章能帮你理解这个链表操作的小技巧！