82.删除排序链表中的重复元素 II
#链表 2024-08-16 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode* virtualHead = new ListNode(-101);
        virtualHead->next = head;
        ListNode* slow = head;
        ListNode* fast = head->next;
        ListNode* delPre = virtualHead; // 待删除节点的前一个节点

        while(fast){
            if(slow->val != fast->val){ // 如果不相等，三个指针集体前移
                delPre = delPre->next;
                slow = slow->next;
                fast = fast->next;
                continue;
            }
            while(fast != nullptr && slow->val == fast->val){   // fast 最终指向 不重复节点的位置
                fast = fast->next;
            }
            if(fast != nullptr){    // 删除重复节点
                delPre->next = fast;
                slow = fast;
                fast = fast->next;
            }else{  // 如果 fast 为空，表明slow 和 fast 之间都是重复值，delPre 指向 fast 就代表删除这些重复值
                delPre->next = fast;
            }

        }

        return virtualHead->next;
    }
};

当我们的链表中删除某个节点，如果这个节点可能包含头结点，那么务必使用虚拟头结点，因为删除节点需要拥有待删除节点的前一个节点才能进行删除。