【数据结构基础

原题连接：Leetcode 82. Remove Duplicates from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

首先链表是有序的
那么重复的元素一定就在一起，设置两个指针：

• pre：指向已经完成删除的部分的结尾
• cur：用于跳过存在重复结点的区间（也就是删除）

因为头结点也有可能删除，添加一个虚拟头结点

举个例子： 以 112334 为例

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 提前返回的情况
        if (!head || !head->next) 
            return head;

        // 虚拟头结点
        ListNode* preHead = new ListNode(0);
        preHead->next = head;
        
        // 两个指针，用于找到重复元素的区间
        ListNode* pre = preHead;
        ListNode* cur = head;

        while (cur) {
            // 如果cur处于重复元素区间中，则将cur移动到当前重复元素所在区间的最后一个结点
            while (cur->next && cur->val == cur->next->val) {
                cur = cur->next;
            }
            // pre和cur之间没有重复节点，pre后移
            if (pre->next == cur) {
                pre = pre->next; 
            } 
            // 之间隔着重复结点区间
            else {
            	// 跳过重复元素的区间
                pre->next = cur->next;
            }
            cur = cur->next;
        }
        return preHead->next;
    }
};

• 时间复杂度：O(n)，遍历一遍链表
• 空间复杂度：O(1)，常数个临时变量