单链表操作之--删除带头结点的单链表中所有值为X的元素

如题所述

第1个回答  2022-07-01

删除带有头结点的单链表所有值为X的元素,算法主要思想如下:
用结点指针 p 从第一个 元素结点 开始遍历链表,若结点值为X,则进行删除操作,并释放被删结点空间。
因为是单向链表,所以仅 p 指针无法直接找到值为X结点的前驱,需要用一个 pre 指针,始终指向p的前驱,即 pre->next = p ,同时因为需要释放空间,还需要一个辅助指针 q 来释放被删结点空间,
当p不为空时 ,即单链表 L 不为空
初始化 pre, p 指针后的状态

p 当前所指结点值为X,若要删除掉当前结点:
1.) 首先将 p 指针复制给 q ,待当前结点从链表中删除后 通过 free(q) 来释放空间,如图所示状态,此时 p q 指针同时指向值为x的元素结点

2.) p 复制给 q 之后, p 便直接指向下一个结点,即 p = p->next

3.)这时 当前值为X的结点已经从链表中删除掉了,可以释放掉其空间,通过 free(q) 语句

链表删除部分的语句还可以这样实现:

while循环执行如上过程便可以实现删除带头结点的单链表中所有值为X的元素
一个简单的C语言实现