Java怎么删除链表中重复的结点

本篇内容主要讲解"Java怎么删除链表中重复的结点"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"Java怎么删除链表中重复的结点"吧!

核心考点：链表操作，临界条件检查，特殊情况处理

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

解析一：（不提倡）

解决该问题较简单，且在写代码时不易出错的做法如下：

1. 遍历一遍链表，记录重复结点的结点值。

2. 再遍历一遍链表，逐个删除重复结点。

该方法需要遍历两遍链表，且需要开辟额外的内存空间存储重复结点的结点值，所以一般不提倡。

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) :        val(x), next(NULL) {    }};*/class Solution {public:    ListNode* deleteDuplication(ListNode* pHead) {        if(pHead == nullptr||pHead->next == nullptr) //链表为空或只有一个结点无需进行操作            return pHead;        ListNode* cur = pHead;        unordered_set filter;                //1、遍历链表找出重复的结点，将结点值存入filter                while (cur->next)        {                        if (cur->val == cur->next->val)                                filter.insert(cur->val);                        cur = cur->next;        }                //2、逐个删除重复的结点        //先删除头部的重复结点        while(pHead&&filter.find(pHead->val) != filter.end())        {            pHead = pHead->next;        }        if(pHead == nullptr)            return nullptr;        //再删除其余的重复结点        ListNode* prev = pHead;        ListNode* last = prev->next;        while(last)        {            if(filter.find(last->val) != filter.end())            {                prev->next = last->next;                last = last->next;            }            else            {                prev = prev->next;                last = last->next;            }        }        return pHead; //返回链表头指针    }};

解析二：（正解）

我们当然应该尽可能在遍历一遍链表的情况下解决该问题，这时我们需要使用两个指针配合完成，该过程当中包含大量细节，大致步骤如下：

1.为了后续操作方便，先为该链表创建一个头结点。

2.使用指针prev和last遍历链表，初始时prev指向头结点，last指向头结点的下一个结点。

3.当last指向的结点值与其后一个结点的结点值相同时，last独自后移，直到last指向结点的结点值与其下一个结点的结点值不同为止，此时让prev指向的结点指向last的后一个结点，最后让last指向下一个结点（图中未后移）。

4.当last指向的结点值与其后一个结点的结点值不同时，prev和last一同向后移。

如此进行下去，直到last将链表遍历完，链表当中重复的结点也就全部被删除了，最后返回头结点指向的链表即可。

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) :        val(x), next(NULL) {    }};*/class Solution {public:        ListNode* deleteDuplication(ListNode* pHead) {                if (pHead == nullptr || pHead->next == nullptr) //链表为空或只有一个结点无需进行操作                        return pHead;                ListNode* head = new ListNode(0); //创建头结点（便于操作）                head->next = pHead; //头结点与原链表建立关系                ListNode* prev = head;                ListNode* last = prev->next;                while (last)                {                        //未发现重复的结点，prev和last一同后移                        while (last->next&&last->val != last->next->val)                        {                                prev = prev->next;                                last = last->next;                        }                        //发现重复的结点，last独自后移                        while (last->next&&last->val == last->next->val)                        {                                last = last->next;                        }                        //到达此处有三种情况：                        //1、没有需要删除的重复结点，是因为last->next == nullptr到此                        //2、有需要删除的重复结点，是因为last->next == nullptr到此（链表后半段都需要删除）                        //3、有需要删除的重复结点，是因为last->val != last->next->val到此（链表中间某段需要删除）                        if (prev->next != last) //说明有需要删除的重复结点                        {                                prev->next = last->next;                        }                        last = last->next;                }                return head->next; //返回链表头指针        }};

到此，相信大家对"Java怎么删除链表中重复的结点"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！