[M链表] lc82. 删除排序链表中的重复元素 II(单链表+好题+模拟)

1. 题目来源

链接：82. 删除排序链表中的重复元素 II

相似题目：[E链表] lc83. 删除排序链表中的重复元素(单链表+模拟)

2. 题目解析

这个题目与 83 题都很类似，一个是将重复元素全部删除，另一个是将重复元素至多保留一个。注意以下几点即可：

• 本题可能一个节点都不存在，且头结点也可能被删除发生改变。所以需要应用到虚拟头结点的这个技术。
• 我们需要在链表中找到值相同的这一段链表，首位指针分别用 a,b 来标识，那么构成一个 [a, b) 区间，例如:1->2->3->3->3->4->NULL 链表，那么此时 a–>3（1），b指向4。显然，我们只需要让 a 的前一个指针的 next 指向 b 指针位置，即 a->next=b 即可。所以我们需要知道，3 的前一个位置，即 2 所在位置的指针。如果 2 的next的next 指针元素 b 与 2 的next 指针 a 一致，那么 b 指针向后移动，过滤掉重复元素，直到不相等的时候，现在有两种可能的情况：
  • 中间是没有重复元素的，不需要跳过重复元素
    • 没有重复元素，意味着 2 的 next 的 next 元素与 b 一致。此时就没有跳过任何元素，则 2 的这个指针向后一定一位即可。
  • 中间是有重复元素的，需要跳过重复元素
    • 反之，2 的这个指针需要指向 b 指针，跳过中间的重复元素。
• 最终返回虚拟头结点的 next 指针即可
  
  注意体会两点：
• 找到重复元素段后，针对当前节点的 next 指针赋值，要区分情况。有重复段和无重复段，next 指针指向的位置是不一样的。
• 比较两个链表元素节点是否一样，应该直接用 节点之间的 ==，而不是 val 的 == 哈

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

// @lc code=start
/**
 * 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* dummy = new (ListNode){0, head};
        ListNode *a = dummy;
        while (a->next) {
            ListNode *b = a->next->next;
            while (b && (b->val == a->next->val)) b = b->next;
            if (a->next->next == b) a = a->next;
            else a->next = b;
        }

        return dummy->next;
    }
};
// @lc code=end