程序员面试金典 - 面试题 02.03. 删除中间节点

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。

示例：

• 输入：单向链表 a->b->c->d->e->f 中的节点 c
• 结果：不返回任何数据，但该链表变为 a->b->d->e->f

题目思考

1. 如何在常数时间内删除?

解决方案

思路

• 根据题目限制, 不能拿到上一个节点, 所以无法通过将上一个节点的 next 指向删除节点的 next 的做法来删除
• 但是我们可以换种思路, 既然可以拿到当前节点的 next, 那么只需要将当前节点的值设置为它 next 的值, 然后删除 next 节点, 从而达到一样的效果
• 因为删除节点不是最后一个节点, 这样就保证了它 next 节点一定有值

复杂度

• 时间复杂度 O(1): 只需要两个常数操作
• 空间复杂度 O(1): 没有使用额外变量

代码

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        # 将next节点的值赋给当前节点
        node.val = node.next.val
        # 删除next节点
        node.next = node.next.next

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊