本文主要是介绍力扣82题删除排序链表中的重复元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
82题删除排序链表中的重复元素
题目描述
给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。
题目分析
- 这个题需要返回已排序链表,我们需要考虑一种情况就是头结点为重复元素,那么我们把头结点删除之后没有办法再找到之后的节点了,这个时候我们需要设置一个虚头节点,来保证即使头结点删除了我们也能找到之后的节点
- 我们需要新建一个指针cur指向虚头节点
- 明确删除节点的操作就是将他的前驱节点与后继节点相连接,所以我们需要保证cur->next 与cur->next->next不为空,这个顺序不能乱
- 当找到cur->next->val=cur->next->next->val的时候,我们需要将这个值记录一下,用p记录一下这个值,这个值在后续可能还会出现的,如果cur->next->val!=cur->next->next->val的话,cur往后走一步
- 再次遍历后续链表将cur->next不为空且cur->next->val的值等于我们标记的值证明我们找到了重复的值,cur->next=cur->next->next 进行删除操作
- 我们这样就完成了这个过程,返回h->next即可。
-
创建虚头节点
这时cur->next->val=cur->next->next->val
将3标记为x,进行删除操作
这时cur的位置并没有发生改变,cur->next->val=cur->next->next->val=4
[cur->next指向5的时候,cur->next->next为空,跳出循环,完成整个删除过程
代码
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(!head)return head;ListNode*h=new ListNode();h->next=head;ListNode*cur=h;while(cur->next&&cur->next->next){if(cur->next->val==cur->next->next->val){int p=cur->next->val;while(cur->next&&cur->next->val==p){cur->next=cur->next->next;}}else{cur=cur->next;}}return h->next;}
};
这篇关于力扣82题删除排序链表中的重复元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!