删除链表中的重复元素

阳光穿透心脏的1/2处 2023-11-08 06:59 292阅读 0赞

题目详情：

给定 1->2->3->3->4->4->5, 返回 1->2->5.  
给定 1->1->1->2->3, 返回 2->3

分析  
这类问题一般都要特地构造一个头部，比如说

1 -> 1 -> 2 -> 3 -> NULL  
1  
这个时候如果把1删掉了，那么head放在哪？相反，如果是

x -> 1 -> 1 -> 3 -> NULL  
1  
这样的话，把1都删掉了，x还可以充当头部，不管取什么值都可以，反正最后返回的肯定是

return x->next;  
1  
不知道我排版得有没有对齐，应该不影响阅读吧。反正核心思想是，如果p所在的位置和下一个位置的值相同，就一直往后走。而且走到最后一个3的时候，记得还要再走一步才能到4。

那么c和p之间如何跨越这么大的鸿沟呢，最后一句c->next = p，就将它们有紧密的联合起来了，绝对是一对好CP，这也是我给它们这样命名的原因。

之所以要设定这么一个CP，就是因为在这里不像上一题一样，删除重复节点的时候是都要删掉，不会留下一个。换句话说，如果是每次只删一个，最后肯定会有一个留下没有被删除，因为它前后重复都删掉了，剩下继续比较的都是不重复的。因此应该加一个标记，用于最后一次性删除。这里的删除也就是跳过一个节点。

class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
        if(!head||!head->next)return head;
           
        ListNode* dummy=new ListNode(0);
        dummy->next=head;
        ListNode* c=dummy;
        ListNode* p=c->next;
       while(c->next&&c->next->next)
       {
           if(c->next->val==c->next->next->val)
           {
               p=p->next;
               {
                   while(p->next&&p->val==p->next->val)
                       p=p->next;
               }
               c->next=p->next;
           }
           else
           {
               c=c->next;
               p=p->next;
           }
               
       }
            return dummy->next;
    }
    };