题解 | #删除链表中重复的结点

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    unordered_map<int,int> hash;
    ListNode* deleteDuplication(ListNode* pHead) {
        if(!pHead) return NULL;
        ListNode* p=pHead;
        while(p){ // 记录每个值的个数
            hash[p->val]++;
            p=p->next;
        }
        ListNode* newHead=new ListNode(0);
        newHead->next=pHead;
        ListNode* i=newHead;
        ListNode* j=pHead;
        while(j){
            if(hash[j->val]>1){
                j=j->next; //如果该节点值个数大于1则往下走
            }
            else{
                i->next=j; //满足个数只有一个让i指向j
                i=j;    //保存该节点
                j=j->next;    //往下遍历
            }
        }
        i->next=NULL;
        return newHead->next;
    }
};

时间复杂度：O(N)

思路:

代码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead==NULL||pHead->next==NULL){ //若该节点为空或者只有一个节点则返回该节点
            return pHead;
        }        
        while(pHead && pHead->next && pHead->val==pHead->next->val){ //找到以该节点为其点第一个不重复的节点
            while(pHead && pHead->next && pHead->val==pHead->next->val){
                pHead=pHead->next;
            }
            pHead=pHead->next;
        }
        if(pHead) pHead->next=deleteDuplication(pHead->next); //使找到的那个节点指向下一个满足的节点
        return pHead;
    }
};