思路:p指针指向重复元素的前一个节点,q指针指向重复元素的后一个节点。
举例说明如下图:
代码
时间复杂度:$O(N)$
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
auto dummy = new ListNode(0, head), p = dummy;
while (p->next)
{
auto q = p->next;
while (q && p->next->val == q->val) q = q->next; //这里q最少也要前进一步
if (p->next->next == q) p = p->next; //p的下下个元素等于q,即没有相同元素,p指针前进一步
else p->next = q; //存在相同元素,p直接跳到q
}
return dummy->next;
}
};