写在前面

剑指offer：删除链表中重复的结点

题目要求

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

解法

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(!pHead||!pHead->next) return pHead;
        ListNode* newHead = new ListNode(0), *cur = pHead;
        newHead->next = pHead;
        unordered_map<int,int> table;
        while(cur) {
            table[cur->val] += 1;
            cur = cur->next;
        }
        cur = pHead;
        ListNode* pre = newHead;
        while(cur) {
            if(table[cur->val]>1) {
                ListNode* temp = cur->next;
                pre->next = cur->next;
                delete cur;
                cur = temp;
            }
            else {
                pre = cur;
                cur = cur->next;
            }
        }
        ListNode* res = newHead->next;
        delete newHead;
        return res;;
    }
};

分析：
其实牛客网的题目的描述有点问题，重复的结点是指的就是给出的例子当中的连续出现的重复val的结点，还是说给出的例子只是某一种特例，重复就是指val相同的结点？
我一开始的写法就是当做删除所有重复val的结点。先遍历一遍链表，记录所有元素出现的次数，第二次遍历链表的同时，删除所有重复的结点。
注意的是，很可能原始的头结点会被删除，所以建立一个虚拟的新的头部节点解决这个问题。别忘记delete。

结果发现实际上就是第一种情况，重复val的结点只会连续出现，没必要考虑的这么麻烦。
删除操作只需要往后维护一个next如果和cur的值相等就一直往后走直到第一个和cur不同的结点然后执行删除操作。下面是牛客网的一个别人的答案，为什么要贴出来，因为这个人的删除就是简单的指针链接操作，如果原始的链表结点是new出来的他这个删除其实就是内存泄漏，同时他的新的头结点也没有释放。。。

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
          if(pHead==NULL||pHead->next==NULL) return pHead;
          else
          {
              //新建一个节点，防止头结点要被删除
              ListNode* newHead=new ListNode(-1);
              newHead->next=pHead;
              ListNode* pre=newHead;
              ListNode* p=pHead;
              ListNode* next=NULL;
              while(p!=NULL && p->next!=NULL)
              {
                  next=p->next;
                  if(p->val==next->val)//如果当前节点的值和下一个节点的值相等
                  {
                      while(next!=NULL && next->val==p->val)//向后重复查找
                          next=next->next;
                    pre->next=next;//指针赋值，就相当于删除
                    p=next;
                  }
                  else//如果当前节点和下一个节点值不等，则向后移动一位
                  {
                      pre=p;
                      p=p->next;
                  }
              }
           return newHead->next;//返回头结点的下一个节点

          }
    }
};