题解 | #删除有序链表中重复的元素-II#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if (!head || !head->next) return head;
        // 老套路了，创建 dummy 节点接到头节点前面
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;

        // 双指针做法，prev 指向重复节点出现前的最后一个节点
        // current 指向重复节点里的最后一个节点
        while (prev->next) {
            ListNode* current = prev->next;
            bool isDuplicate = false;

            // current 在遇到重复值节点的时候一直往后遍历，直到后面节点的值和前面一串重复值都不一样
            // 或者就是已经到最后一个节点了，没法再往后遍历了
            while (current->next && current->val == current->next->val) {
                isDuplicate = true;
                current = current->next;
            }

            if (isDuplicate) {
                // 一串重复节点前的在最后一个节点，直接接到这一串重复节点后面的节点上
                prev->next = current->next;
            } else {
                // 目前没有重复，prev 还没移动到定义的位置上，还得往后遍历
                prev = prev->next;
            }
        }

        return dummy.next;
    }
};