复习链表的插入
链表的一个节点是由数据域和指针域构成,指针域的地址值为下个元素的地址。那么我们需要插入或者删除一个元素怎么处理呢?
- 此时我们需要先保存n节点的地址(300),n节点的地址存放在m节点的指针域,将此值赋值给x节点的指针域。(x->next=m->next),变成了下图所示。
- 此时再将m节点和x节点连接起来。m->next=x.如下图所示。
看到这里,有些小伙伴可能会有疑问了。如果是空链表,这样的插入方式就行不通的了呀(自己可以画图看看哈),对,这就是要说的重点了,哨兵。
我们可以先思考导致空链表不能使用第一种方案的原因,因为它没有结点,我们自然无法获取其地址,所以采用增加一个头结点,那么此时空链表的结构如下图4,非空链表结构如下图5.
复习链表的删除
- 上面简单介绍了带头结点的链表,在删除处理的时候同样适用,所以我们以后就直接采用带头结点的链表讲解。下面直接看看删除节点图。
1 Leetcode237 删除链表的节点
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9],它可以表示为:
示例1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
说明:
- 链表至少包含两个节点。
- 链表中所有节点的值都是唯一的。
- 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
- 不要从你的函数中返回任何结果。
先思考一分钟哟!
效果更好哈!
01 题目解析
- 常规套路
- 找到待删除结点的上一个结点的指针。
- 将指针指向待删除的下一个结点。如下图7所示。
- 仔细看题
- 发现没,题目并没有告诉我们其上一个结点,不要紧,我们可以想办法构造出一个结点,请看下。
- 目标还是删除5,最后结果为[4,1,9]。我们把需要删除的5结点的后面节点1赋值给它,如下图8.
02 代码实现
1 c++版本
2 python版本
3 java版本