解题思路

• 先创建一个新的结点，这个是为了后续能方便指向链表的第一个元素；
• 以当前结点的下一个和下下一个是否存在作为条件进行循环遍历。如果当前连着的两个元素值相同，则利用一个循环删除重复的元素。
• 最后返回新节点的next元素即可。

关键：对链表的定义要十分熟悉。

复杂度

• 时间复杂度为O(N)；
• 空间复杂度为O(1)。

代码

Python

class Solution:
    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        if pHead is None:
            return pHead

        res = ListNode(-1)
        res.next = pHead

        cur = res

        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                tmp = cur.next.val
                while cur.next and cur.next.val == tmp:
                    cur.next = cur.next.next
            else:
                cur = cur.next

        return res.next

C++

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {

        ListNode* res = new ListNode(-1);
        res->next = pHead;
        ListNode* cur = res;


        while(cur->next && cur->next->next)
        {
            if(cur->next->val == cur->next->next->val)
            {
                int tmp = cur->next->val;
                while(cur->next && cur->next->val == tmp)
                {
                    cur->next = cur->next->next;
                }
            }
            else
            {
                cur = cur->next;
            }
        }

        return res->next;

    }
};