删除有序链表中重复的元素-II

问题

出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。

思路

利用快慢双指针，fast 去探测非重复元素，slow 负责记录非重复元素。

代码实现

/** * struct ListNode { * int val; * struct ListNode *next; * }; */

class Solution {
    
public:
    /** * * @param head ListNode类 * @return ListNode类 */
    ListNode* deleteDuplicates(ListNode* head) {
    
        // write code here
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead->next;
        while (fast && fast->next)
        {
    
            // 下一个节点 != 当前节点，当前节点不是重复元素
            if (fast->next->val != fast->val)
            {
    
                // fast 探测到的不是重复节点，因此 slow 可以直接往前挪
                slow = fast;
                fast = fast->next;
            }
            else
            {
    
                // fast 探测到重复元素，记录重复元素，并向前挪
                int repeatVal = fast->val;
                // fast 不等于重复元素，退出循环，不能保证该节点不是重复节点
                // 如：1 2 2 3 3，还要继续比较 fast 和下一个元素
                while (fast && fast->val == repeatVal)
                {
    
                    fast = fast->next;
                }
                
                slow->next = fast;
            }
        }
        return dummyHead->next;
    }
};