首先看一道更简单的
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/submissions/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == nullptr) return head;
ListNode* tmp = head;
while(tmp->next != nullptr){
if(tmp->val == tmp->next->val){
tmp->next = tmp->next->next;
}else{
tmp = tmp->next;
}
}
return head;
}
};
然后是这道题,由于链表的头节点可能会被删除,因此我们需要额外使用一个哑节点(dummy node)指向链表的头节点。我们从指针 cur\textit{cur}cur 指向链表的哑节点,随后开始对链表进行遍历。如果当前 cur.next\textit{cur.next}cur.next 与 cur.next.next\textit{cur.next.next}cur.next.next 对应的元素相同,那么我们就需要将 cur.next\textit{cur.next}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) {
if(!head) return head;
ListNode* dummy = new ListNode(-1, head);
ListNode* cur = dummy;
while(cur->next && cur->next->next){
if (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 dummy->next;
}
};