题目链接：LeetCode 82. 删除排序链表中的重复元素 II

一、题解

同样又是一道熟悉的链表题目：题目要求将有重复的节点全部删掉！

这道题还是比较好想的：

如下图：

为了统一该链表，防止第一个节点就是重复节点导致，头结点的改变，我们使用虚拟头结点指向该头节点，实现统一操作！

  1. 用一个指针p指向当前节点，另一个指针q指向下一个节点
  2. 接下来，q从p->next开始，一直走到第一个与p->next不同元素的位置，这时有两种情况：
    1. p->next->next == q：则说明p后面没有重复元素，直接后移p = p->next
    2. p->next->next != q：则说明p后面有重复元素，则跳过这一堆重复元素，p直接指向q即可，p->next = q
  3. 最后返回dummy->next即可

时间复杂度：O(n)

空间复杂度：O(1)

二、AC代码

参考代码：

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
/**
 * 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) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto p = dummy;
        while(p->next){
            auto q = p->next;
            while(q && p->next->val == q->val) q = q->next;
            if(p->next->next == q) p = p->next;
            else p->next = q;
        }
        return dummy->next;
    }
};