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

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

数据范围

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

样例1

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

样例2

输入：1->1->1->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错误，记住！）

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

创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖