1.题目

题目地址(82. 删除排序链表中的重复元素 II - 力扣（LeetCode）)

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/

题目描述

给定一个已排序的链表的头 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
• 题目数据保证链表已经按升序 排列

2.题解

2.1 一次遍历

思路

1.首先注意是否需要处理空链表情况？ 这里 *cur = head, cur != nullptr 即可以避免空链表的情况
2.是否需要虚拟头结点？是，因为可能出现需要删除链表头部元素的可能
3.需要几个节点？首先要一个prev保存上一个非重复元素位置； 其次我们需要一个cur用来表示当前位置， 可能还需要一个临时节点tempy用于更新链表（便于删除）
4.对于出现重复值和没有出现重复值的处理是不一样的，我们需要进行不同的处理：
4.1对于没有出现重复值的话，我们直接将prev和cur都往后移动即可
4.2对于出现重复值的情况，我们保持prev不动，向后移动cur（同时删除当前cur节点）直到:

• 1.cur的值和下一个值不同为止；
• 2.没有下一个值了 cur->next == nullptr;
  到这时，我们发现会剩下最后一个重复节点有删除，进行单独处理，同时更新prev的值

5. 终止条件

• 1.删节点删的 cur == nullptr， 比如像[1,2,5,5,5], 最后的几个节点均是重复节点，删除之后 cur == nullptr
• 2.前一步是正常后移， prev = cur, cur = cur->next; 但是没有下一个值了，不存在重复节点的问题，直接结束

代码

• 语言支持：C++
  C++ Code:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummyHead = new ListNode(0, head);
        ListNode *prev = dummyHead, *cur = head;
        // 首先保证cur != nullptr, 才可能有cur->next, 不然会报错访问空指针
        while (cur != nullptr && cur->next != nullptr) {
            if (cur->val == cur->next->val) {
                // 处理重复节点（后面一个指针不为nullptr,才有可能存在重复节点问题）
                while (cur->next != nullptr && cur->val == cur->next->val) {
                    ListNode* temp = cur;
                    cur = cur->next;
                    delete temp;
                }
                // 处理最后一个重复节点
                ListNode* temp = cur;
                cur = cur->next;
                prev->next = cur; // 更新prev->next
                delete temp;
            } else {
                prev = cur;
                cur = cur->next;
            }
        }
        return dummyHead->next;
    }
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：\(O(n)\)
• 空间复杂度：\(O(1)\)

总结

这题最麻烦的是弄清楚究竟什么时候终止，有哪些可能的情况，尤其是我们讨论 cur->next这种下一个节点的时候，要考虑到有没有可能当前节点cur就是空指针了