删除链表中所有重复的结点

题目描述

解题思路：

• 对于删除类的问题需要特别注意的一个点就是链表的头节点，头节点也可能是被删除的结点，所以一般在这种删除类的问题里面，我们都会给出一个伪头结点，为了防止传递二级职责和你这种麻烦的情况出现，首先需要建立一个伪头结点。
• 接下来，就需要我们去遍历整个链表了，如果说当前节点的值与他的下一个结点的值相等的话，那么他们两个就是都需要被删除的了，为了保证删除之后的链表仍然是相互连接在一起的，我们需要把当前结点的前一个结点和后面值比当前结点大的结点进行项链接，我们要确保当前节点始终与下一个没有重复的结点连接在一起。

/*
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;
          else
          {
              //新建一个节点，防止头结点要被删除
              ListNode* newHead=new ListNode(0);
              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;//返回头结点的下一个节点
               
          }
    }
};