Acwing 29.删除链表中的重复值（结点）

在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。

数据范围

链表中节点 val 值取值范围 [0,100]。

链表长度 [0,100]。

样例1

1. 输入：1->2->3->3->4->4->5
2. 
3. 输出：1->2->5

样例2

1. 输入：1->1->1->2->3
2. 
3. 输出：2->3

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        ListNode *pre = dummy,*cur = head,*tmp;
        while (cur)
        {
            tmp = cur;
            while (tmp->next&&cur->val ==tmp->next->val) tmp = tmp->next;
            if (cur == tmp)//说明只有一个重复值
            {   
                pre->next = cur;//链接上去
                pre = pre->next;//更新Pre
            }
            cur = tmp->next;
        }
        pre->next = nullptr;
        return dummy->next;
    }
};

问题分析：

第一步：采用双指针：判别是否加入某个节点，cur和tmp,若tmp经过while循环后依旧等于cur ,那么说明当前cur这个结点所对应的值的区间长度为1，cur可以被加入到最终的链表；

第二步：创建一个前驱结点pre，用来更新最终链表的链接关系，

如果cur是符合题意的,那么pre的后继就可以设为cur,否则不建立后继关系；

无论是否建立后继关系，[cur,tmp]这个区间内表示所有val = cur->val的结点，区间长度只影响是否建立后继关系，那么此时，需要将cur移动到新的val即tmp->next处，循环往复；

第三步：细节处理，如果要建立后继结点关系，需保证后继结点非空，如果最后两个结点刚好是重复的x，按照我们上面的步骤，是没有建立节点关系的（没有更新），那么此时的pre的后继节点仍然是x（因为所有结点是基于原链表的关系，我们只不过更改了相互之间的连接关系），那么我还需要在最后一步，使得最后的pre指向空；还有一种极端的情况，全部都删掉了，因此我们需要创建一个虚拟头节点，并使得它的next指向null，此时的虚拟头节点不进入while循环也就是等于pre，也恰好符合我们上面的特殊情况；

       一些小知识点："=="的优先级高于&,写与运算&&的时候，前后的次序很重要（这道题我就是因为while循环的与顺序写反了一直出现segmentation fault错误，记住！）

我是小郑，正在奔赴热爱，奔赴算法，奔赴山海，大厂未来有我！