Python | 删除链表的节点问题解决方法

作者: 算法与编程之美  更新时间:2021-05-20 00:29:37  原文链接


本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

问题描述

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

示例 1:

输入 : head = [4,5,1,9], val = 5

输出 : [4,1,9]

解释 : 给定你链表中值为  5  的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:

输入 : head = [4,5,1,9], val = 1

输出 : [4,5,9]

解释 : 给定你链表中值为  1  的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

解决方案

首先要知道基本的链表知识, 若结构是非空有限集,有且仅有一个开始节点和一个终端节点,并且所有节点都最多只有一个 直接前趋 和一个 直接后继

可表示为:( a 1  ,  a 2    , ……,    a n

线性结构表达式:( a 1  ,  a 2 , ……,    a n

特点是 只有一个首节点和尾节点, 除首尾 点外,其他 点只有一个直接前驱和一个直接后继。 简言之,线性结构反映节点间的逻辑关系是一对一的。

本题是对单链表的基本操作,有一些 符号表示要注意

n1# 表示第一个节点

n1.next# 表示第一个节点的下个节点也就是n 2

#赋值操作

n1.data=1

n2.data=2

n1.next=n2

n2.next=n3

解决本题主要分为两步, 1.找到目标节点,遍历链表,直到h ead.val==val 时跳出,即找到目标节点。 2.修改引用,假设bef为前节点,则bef .next 为后继节点,当执行 b ef.next=bef.next.next 时,即可实现删除 b ef.next 节点。注意,当应删除头节点 head时,直接返回h ead.next 即可。最后返回链表头部节点 h ead 即可。

class Solution:

def deletenode(self,head:listnode,val:int) -> listnode:

if head.val==val:

       return head.next

   bef=head

   while bef.next:

       if bef.next.val=val:

           bef.next=bef.next.next

           break

       bef=bef.next

   return bead

结语

删除链表的节点需要我们学习不同的知识点。在后续的学习中我们要抓住链表相关的内容进行巩固所学知识点!

不足之处在于自己还没有熟练掌握这方面的知识点,而是大部分上网查找所得资料。后面要学习自己熟练掌握知识点。

我们下一次准备写与《数据结构与算法》相关的内容,敬请期待!

实习编辑:李欣容

作者: 欧洋、赵甜、巨金玲

稿件来源:深度学习与文旅应用 实验室(DLETA)