[数据结构与算法]JZ76 删除链表中重复的结点

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

数据范围：链表长度满足 ，链表中的值满足

进阶：空间复杂度 ，时间复杂度

例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：

示例1
输入：
{1,2,3,3,4,4,5}
返回值：
{1,2,5}
示例2
输入：
{1,1,1,8}
返回值：

遍历

定义三个指针变量，第一个指向NULL，第二个指向(cur)第一个元素，第二个指向第二个(next)，分别判断,cur和next,如果两个值不相同就整体往后移，如若相同，则next一直向后移，直到不相同，并去除相同的元素，直到链表结束。

struct ListNode* deleteDuplication(struct ListNode* pHead ) {

    struct ListNode* prev=NULL;
    struct ListNode* cur=pHead;
    struct ListNode* next=pHead->next;
    if(pHead==NULL||pHead->next==NULL)
        return pHead;
    while(next)
    {
       if(cur->val!=next->val)
       {
           prev=cur;
           cur=next;
           next=next->next;
       }
       else
       {
          while(next&&cur->val==next->val)
          {
            next=next->next;
          }
          if(prev)
          {
              prev->next=next;
          } 
           else
           {
               pHead=next;
           }
           
          while(cur!=next)
          {
              struct ListNode* del=cur;
              cur=cur->next;
              free(del);
          }
           if(next)
           {
                next=next->next;
           }
           
       }
    }
    return pHead;
}