链表OJ（七）删除有序链表中重复的元素-I -II

目录

删除有序链表中重复的元素-I

删除有序链表中重复的元素-II

---

删除有序链表中重复的元素-I

描述

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→21→1→2,返回1→21→2.
给出的链表为1→1→2→3→31→1→2→3→3,返回1→2→31→2→3.

【解法一】哈希遍历删除（该方法下面俩道题均适合）

哈希表遍历一遍，对每个元素出现次数统计，然后再遍历第二遍，将结点元素出现次数出现超过俩次的全部删除

【解法二】直接删除

 使用哑结点pre来进行删除，如果pre与cur值相等，就用pre删掉cur，如果不相等俩个一起后移就行

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {// write code hereauto newhead = new ListNode(-1);newhead->next = head;auto pre = newhead, cur = head;while(cur){if(cur->val == pre->val){pre->next = cur->next;    // 相等进行删除cur = pre->next;}else {pre = pre->next;    // 不相等后移cur = cur->next;}}return newhead->next;}
};

 删除有序链表中重复的元素-II

描述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→51→2→3→3→4→4→5, 返回1→2→51→2→5.
给出的链表为1→1→1→2→31→1→1→2→3, 返回2→32→3.

【解法一】直接删除

 利用pre来删除后面有相等元素的结点，每次循环定义一个Next，利用Next与cur进行比较，如果如果Next的值等于cur，那么Next不断后移（注意Next判空存在），直到找到一个nullptr或者与cur不相等的结点为止，利用pre删除中间相等的结点

 直到找到一个nullptr或者与cur不相等的结点为止，利用pre删除中间相等的结点

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {// write code hereListNode* newhead = new ListNode(-1);newhead->next = head;auto pre = newhead, cur = head, Next = head;while(cur){Next = cur->next;if(Next && cur->val == Next->val){while(Next && cur->val == Next->val){Next = Next->next;    // Next遍历至最后一个不相等结点或者空节点}pre->next = Next;    // 利用pre进行删除cur = Next;        // 更新cur}else {pre = pre->next;    // 如果俩结点不相等，cur pre一起后移cur = cur->next;}}return newhead->next;}
};

【解法二】哈希遍历删除

哈希表遍历一遍，对每个元素出现次数统计，然后再遍历第二遍，将结点元素出现次数出现超过俩次的全部删除