题目描述

29.删除链表中重复的节点

方法1

线性扫描

添加虚拟元素dummy指向链表头节点，防止错判头节点也被删除的情况。
从前往后扫描整个链表，每次扫描元素相同的一段，如果这段元素个数多于1个，则将整段元素直接删除。

时间复杂度

整个链表只扫描一遍， $O(n)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution{
    public:
    ListNode* deleteDuplication(ListNode* head){
        auto dummy=new ListNode(-1);
        dummy->next=head;
        auto p=dummy;
        while(p->next){
            auto q=p->next;
            while(q->next&&q->next->val==q->val)
                q=q->next;
            if(q==p->next)//没有重复出现的，p后移
                p=q;
            //23344
            //p q
            else
                p->next=q->next;//2->4
        }
        return dummy->next;
    }
};