题目描述

非排序链表也可

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:

    int hash[100100];
    ListNode* deleteDuplication(ListNode* head) {

        if(head==NULL||head->next==NULL)return head;


        ListNode *first=new ListNode(-1);

        first->next=head;

        memset(hash,0,sizeof(hash));

        ListNode *p=first,*pre;

        while(p->next){
            hash[p->next->val]++;
            p=p->next;
        }

        p=first->next;
        pre=first;

        while(p->next){

            if(hash[p->val]>1){

                ListNode *tmp=p;
                pre->next=p->next;
                delete tmp;

                p=pre->next;

            }else{

                pre=p;
                p=p->next;

            }

      }

      if(hash[p->val]>1){
          pre->next=p->next;
      }


      // printf("%d\n",first->next->val);


       return first->next;
    }


};