在单链表中删除值相同的多余结点

科技数码时间：2024-10-26 07:02:06

在单链表中删除值相同的多余结点

在单链表中删除值相同的多余结点，可以采用以下两种方法：

1. 遍历单链表：建一个hash table，遍历单链表，如果此值在hash table中没有就加进去，如果已经有了就删除当前节点。这样，值相同的多余结点就会被删除。需要注意的是，这种方法的时间复杂度为2n，其中n为单链表的长度。

2. 有序单链表中删除重复的结点：在有序单链表中，重复的元素必然相邻。可以定义3个结点指针：ppre、pcur、pdel。pcur作为活动指针，初始指向第一个数据元素的结点，而ppre初始指向pcur的前驱结点，pdel用于指向待删除的结点。用一个循环控制ppre和pcur向后移动，当ppre指向的结点值和pcur指向的结点值相等，那么ppre的指向的位置保持不动，将pcur的指向先传递给pdel，然后pcur向后移一个位置，再将ppre指向的结点作为pcur指向的结点的前驱，这两个结点再次保持相邻，最后释放pdel指向结点的空间，达到删除多余结点的效果。

标签： #科技数码

郑重声明：图文由自媒体作者发布，我们尊重原作版权，但因数量庞大无法逐一核实，图片与文字所有方如有疑问可与我们联系，核实后我们将予以删除。