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

删除链表中重复的结点：最直观的想法是，两次遍历。第一次遍历使用umap存储元素以及元素出现的次数；第二次遍历创建一个头结点作为前一个结点，当前一个结点的下一个结点出现的次数大于1则表明重复，故删掉当前节点，依次类推。最后返回头结点的下一个结点即第一个结点即可。

ListNode* deleteDuplication(ListNode* pHead) {
        // 元素 次数
        unordered_map<int,int> umap;
        ListNode * p = pHead;
        // 统计各元素以及各元素的次数
        while(p)
        {
            umap[p->val]++;
            p=p->next;
        }
        // 头结点
        ListNode * head = new ListNode(0);
        head->next=pHead;
        ListNode * q = head;
        // 指向当前节点
        while(q->next)
        {
            if(umap[q->next->val]>1)
                q->next=q->next->next;
            else q=q->next;
        }
        return head->next;
    }

idea：其实题目中说明该链表为有序链表，那么重复的结点其实就已经紧挨着，所以我们可以利用这一特性来完成。那么如何判断重复呢？假如重复又该如何处理呢？接下来我将依次解决这个问题。首先判断重复我们可以同样的创建一个头结点作为前一个节点，然后判断当前结点的下一个结点值与当前结点的下下一个结点值是否相等；然后处理重复我们可以取出相等的这个值，然后依次判断当前结点的下一个结点值是否等于这个值，如果是则依次删除对应结点，注意，由于重复的不止两个，故我们在删除的这层循环中不要改变前一个结点喔，反之如果相邻元素值不相等则直接后移前一个结点，依次类推。

ListNode* deleteDuplication(ListNode* pHead) 
{
    // 头结点
    ListNode * head = new ListNode(0);
    head->next=pHead;
    ListNode * p = head;
    while(p->next && p->next->next)
    {
       // 相邻元素值相等
       if(p->next->val == p->next->next->val)
       {
          // 取出值
          int val = p->next->val;
          // p保持不变 不断判断p->next喔
          while(p->next && p->next->val==val)
              p->next=p->next->next;
       }
       // 不相等直接后移
       else p=p->next;
    }
    return head->next;
}

注意一点：O(n)可以多次遍历，有时候总是为了追求完美想着一次遍历实现，反而发现再怎么设置数据结构都不行。

注意一点：处理重复，可以取出数值！！