Java删除值相同的多余结点的算法是什么

魁首哥

作者

Java删除值相同的多余结点的算法是什么

本篇内容介绍了“Java删除值相同的多余结点的算法是什么”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

这是一道算法题，写算法题最恨没有图解，懂的人不需要看你的文章，不懂的你再怎么讲解也没有几张图解来得简单易懂，下面来分析一下这道题。

我暂时还没有更好的解决方案，虽然有一个办法解决，但是时间复杂度有点高，先看看我的思路吧。

这是一个无序的单链表，我们采用一种最笨的办法，先指向首元结点，其元素值为2，再遍历该结点后的所有结点，若有结点元素值与其相同，则删除；全部遍历完成后，我们再指向第二个结点，再进行同样的操作。

看图解：

这里有两个指针变量p、q，均指向单链表的首元结点，我们先不移动指针p，而是让指针q去遍历之后的所有结点。

先让指针p指向的结点与后一个结点比较，这里为了操作方便，我们暂且先不移动指针q，而是这样进行比较： p -> data == q -> next -> data；若不相等，则让q指向下一个结点： p = p->next；若相等，则应该先保存下一个结点： r = q -> next，然后让q指针指向下一个结点的下一个结点： q = r -> next，并释放r指向的结点内存。

这样就成功删除了一个与首元结点重复的结点，接下来以同样的方式继续比较，直到整个单链表都遍历完毕，此时单链表中已无与首元结点重复的结点；然后我们就要修改p指针的指向，让其指向首元结点的下一个结点，再让q指向其下一个结点，继续遍历，将单链表中与第二个结点重复的所有结点删除。以此类推，直至指针p也遍历完了整个单链表，则算法结束。

刚才我们已经删除了一个结点，那么接下来p应该指向下一个结点了：

此时让指针p指向的结点与下一个结点的元素值比较，发现不相等，那么让q直接指向下一个结点即可： q = q -> next。

继续让q指向的结点的下一个结点与p指向的结点的元素值比较，发现不相等，此时继续移动q，移动过后q的指针域为NULL，说明遍历结束，此时应该移动指针p。

通过比较发现，下一个结点的元素值与其相等，接下来就删除下一个结点即可：

此时p的指针域也为NULL，算法结束。

代码如下：

LinkListDeleteRepeat(LinkListl){ LinkListp,q,r; p=l->next; while(p!=NULL){ q=p; while(q->next!=NULL){ if(p->data==q->next->data){ r=q->next; q=r->next; free(r); }else{ q=q->next; } } p=p->next; } returnl; }