<>核心考点:链表操作,临界条件检查,特殊情况处理

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

解析一:(不提倡)
解决该问题较简单,且在写代码时不易出错的做法如下:

* 遍历一遍链表,记录重复结点的结点值。
* 再遍历一遍链表,逐个删除重复结点。
动图演示:

该方法需要遍历两遍链表,且需要开辟额外的内存空间存储重复结点的结点值,所以一般不提倡。
/* 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<int>
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; //返回链表头指针 } };
解析二:(正解)
我们当然应该尽可能在遍历一遍链表的情况下解决该问题,这时我们需要使用两个指针配合完成,该过程当中包含大量细节,大致步骤如下:

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

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

*

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

*
当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; //返回链表头指针 } };

技术
友情链接
码工具
Toolsou
API参考文档
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信