题目来源
82. 删除排序链表中的重复元素 II - 力扣（LeetCode）
题目描述
给定一个已排序的链表的头
head， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。示例 1：
输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]示例 2：
输入：head = [1,1,1,2,3] 输出：[2,3]提示：
- 链表中节点数目在范围
[0, 300]内-100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
题目限制
最优解实现题目的解决
思路分析
在处理这个问题时，我们面对的是一个已排序的链表，要求删除所有重复数字的节点，只保留不同的数字。解题的关键在于利用链表已排序这一特性，通过一次遍历完成节点的删除操作。
1. 哨兵节点的引入
- 由于链表的头节点可能会被删除（例如输入链表
[1,1,2]时，头节点1会被删除），所以引入一个哨兵节点（dummy node）。这个哨兵节点的值可以是任意值，但其作用是作为链表的新头，始终指向第一个不重复的节点。这样在处理链表头节点的删除操作时，就无需特殊处理，简化了代码逻辑。
2. 双指针遍历
- 我们使用两个指针，一个指针
prev初始指向哨兵节点，另一个指针curr指向链表的头节点head。 curr指针用于遍历链表，prev指针则用于记录当前不重复节点的前一个节点。在遍历过程中，curr指针不断前进，同时检查curr及其后续节点的值是否与当前curr的值相同。
3. 重复节点的处理
- 当发现
curr的值与下一个节点的值相同时，说明存在重复节点。此时，curr指针需要不断向后移动，直到找到一个与当前值不同的节点，这样就跳过了所有重复的节点。 - 例如，链表为
[1,1,1,2,3]，当curr指向第一个1时，发现下一个节点也是1，curr就一直移动到值为2的节点，此时curr指向了2。 - 然后，将
prev的next指针直接指向curr，这样就跳过了所有重复的节点。即prev原本指向哨兵节点，现在将其next指向2，从而删除了所有值为1的节点。
4. 指针移动
- 在处理完重复节点后，
prev指针移动到curr所在位置，因为curr现在指向的是一个新的不重复节点。而curr指针继续向前移动，准备检查下一组节点。
5. 结束条件
- 当
curr指针遍历完整个链表，即curr为null时，遍历结束。此时，哨兵节点dummy的next指针指向的链表就是删除所有重复节点后的结果链表，直接返回dummy.next即可。
通过这种方法，我们能够在一次遍历链表的过程中，有效地删除所有重复节点，时间复杂度为 ，其中 是链表的长度。同时，由于只使用了有限的额外指针，空间复杂度为 。这种方法简洁高效，充分利用了链表已排序的特性。
具体代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head)return head;
ListNode* cur=new ListNode(-1);
cur->next=head;
ListNode* pre=cur;
while(cur->next&&cur->next->next)
{
if(cur->next->val==cur->next->next->val)
{
int c=cur->next->val;
while(cur->next&&cur->next->val==c)
{cur->next=cur->next->next;}
}
else {cur=cur->next;}
}return pre->next;
}
};这段 C++ 代码定义了Solution类中的deleteDuplicates函数，用于删除已排序链表中重复数字的节点。先判断链表是否为空，空则直接返回。接着创建一个值为 -1 的哨兵节点cur，其next指向原链表头head，pre指向cur。通过while循环，当cur的下一个及下下个节点存在时，若二者值相等，记录该值并跳过所有相同值的节点；否则cur后移。最后返回pre的next，即删除重复节点后的链表头。