LeetCode 每日一题237：删除链表中的节点

今天是一道简单的题目，注意认真审题噢。

题目

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例 1:

示例 2:

说明:

链表至少包含两个节点。链表中所有节点的值都是唯一的。给定的节点为非末尾节点并且一定是链表中的一个有效节点。不要从你的函数中返回任何结果。

链表定义

函数声明

思路

最开始是准备以带头节点的方式, 然后以 的方式删除节点, 但是仔细审题会发现函数声明的参数中只有一个. 这说明是一个不带头节点的链表.

有了这个前提, 算法的思路变成了两步

查找这个结点.

删除这个结点.

问题

根据上面的思路, 如果我们用以往的改变结点 指向的方式的话, 并不太可行. 原因是链表没有前指针, 指针指向的是当前的结点. 另外, 就算把条件设置为 也是不可取的, 因为这时结点在首位的情况会被忽略.

于是我们换个方式, 直接把当前结点用下一个结点替换掉, 这是基于题目中给的给定的节点为非末尾节点这一条件作出的解法.

实现

第一版

Python实现

C实现

第二版

第一版的结果在Python下表现一般, 于是我观摩了一下评论区的大佬, 发现查找部分可以直接省略.

这是为啥?

原因是函数传入的值不是一个数值, 而是一个结点. 已知一个结点, 它的下一个所指也就确定了, 因此直接把结点删除不需要查找了. 最终的答案如下.

Python实现

C实现