82删除排序链表中的重复元素2

82. 删除排序链表中的重复元素 II

下面是题目

下面是题目给出的模板

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

这里给出两种放法，第一种是我通过模仿1171的思路通过unordered_map存储来实现的，第二种是更快的解题方法

第一种

/**
 	这道题，我才用遍历两边的思路完成所有重复节点的删除
 	拿123344556来做实验
 	第一道遍历，将重复的节点删除，但保留重复的第一个节点，同时把3，4，5存储到set中
比如现在，链表已经变成123456了
	第二道遍历，判断节点值是否在set中出现过，如果出现，则删除，比如3，4，5已经在表中了。现在删除他们 最后的得到126
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode*dummy = new ListNode(0);
        dummy->next=head;
        //思路差不多，我也是利用unordered_map 来记录一个是否重复的元素
        set<int>judge;
        if(!head) return NULL;
        ListNode *p = head;
        while( p->next)
        {
            if(p->next->val==p->val)
            {
                p->next = p->next->next;
                judge.insert(p->val);
            }else
                p = p->next;
        }
        p = dummy;
        //第二段遍历，删除存储在set中的节点
        while(p->next)
        {
            if(judge.find(p->next->val)!=judge.end())
              p->next = p->next->next;
			else
               p = p->next;
        }
        return dummy->next;
   }
};

第二种解法

/*
	这个方法也是遍历，但是没有依赖其他容器，而且只遍历了一遍
	思路：
		通过两个指针来实现遍历操作
		下面的题解以12333445为例
		
*/
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* p = new ListNode(0);
        p->next = head;
        head = p;
        while(p->next){
            if(!p->next->next) break;
            //这里把p当作第一个重复节点的前一个结点进行运算，现在p为2，但是接下来是三个相同节点345
            if(p->next->val == p->next->next->val){
                //进入if语句后，把i指向第5个节点。如果第五个节点或者后面的节点还是和第3个节点的值一样，那就移动i，直到不一样位置，再把当前的p节点指向i，完成中间所有重复节点的删除
                ListNode* i = p->next->next->next;
                while(i){
                    if(i->val == p->next->val){
                        i = i->next;
                    }else{
                        break;
                    }
                }
                //更新p后面节点的值，也就是现在p->next =  4,开始下一轮遍历！
                p->next = i;
            }else{
                //更新p的值，寻找下个重复的节点
                p = p->next;
            }
        }
        head = head->next;
        return head;
    }
};