LeetCode 82 删除排序链表中的重复元素 II
🟠 中等 https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/
首先第一个节点也可能被删，因此往前面加一个fakeHead；
链表可以很方便的检查 fast->next->val==val
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head==nullptr) return head;
ListNode* fake_head = new ListNode();
fake_head->next = head;
ListNode* slow = fake_head;
ListNode* fast = head;
int last = slow->next->val;
while(fast&&fast->next!=nullptr){
int val = fast->val;
int count = 0;
while(fast->next&&fast->next->val==val){
fast = fast->next;
count++;
}
if(count==0){
fast = fast->next;
slow = slow->next;
}else{
fast = fast->next;
slow->next = fast;
}
}
return fake_head->next;
}
};
官解
具体地，我们从指针 cur 指向链表的哑节点，随后开始对链表进行遍历。如果当前 cur.next 与 cur.next.next 对应的元素相同，那么我们就需要将 cur.next 以及所有后面拥有相同元素值的链表节点全部删除。我们记下这个元素值 x，随后不断将 cur.next 从链表中移除，直到 cur.next 为空节点或者其元素值不等于 x 为止。此时，我们将链表中所有元素值为 x 的节点全部删除。
如果当前 cur.next 与 cur.next.next 对应的元素不相同，那么说明链表中只有一个元素值为 cur.next 的节点，那么我们就可以将 cur 指向 cur.next。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* fake_head = new ListNode();
fake_head->next = head;
ListNode* cur = fake_head;
while(cur!=nullptr){
if(cur->next&&cur->next->next&&cur->next->val==cur->next->next->val){
int x = cur->next->val;
while(cur->next&&cur->next->val==x){
cur->next = cur->next->next;
}
}else{
cur = cur->next;
}
}
return fake_head->next;
}
};