1. 题目描述

problem link

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

2. 解题

首先，为了应对头节点就是重复节点的特殊情况，还是在链表头部加一个dummyHead。

然后，用一个指针cur指向最后一个已经处理过的节点，初始情况下就是指向dummyHead。再拿一个指针tmp指向当前要处理的节点，并用一个变量val记录下这个节点的值，如下图所示：

然后，就是找后面有没有重复的元素，即让tmp->next的值和val比较，如果相等则让tmp向后走一步然后重复上述判断。对于上图的例子，这一流程走完如下图所示：

然后为了跳过中间重复的1直接让cur->next等于tmp->next就行了。

但假如中间的元素不是重复的，可知这种情况下tmp应该等于cur->next，对于这种情况直接让cur向后走就行了。所以最终这里用一个条件判断区分一下是否重复就行了。

3. 代码

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead == NULL) {
            return NULL;
        }
        ListNode* dummyHead =
            (ListNode *)malloc(sizeof(ListNode));
        dummyHead->next = pHead;
        
        ListNode* cur = dummyHead;
        ListNode* tmp;
        int val;
        
        while(cur->next) {
            val = cur->next->val;
            tmp = cur->next;
            while(tmp->next && tmp->next->val == val) {
                tmp = tmp->next;
            }
            if(tmp == cur->next) {
                cur = cur->next;
            }
            else {
                cur->next = tmp->next;
            }
        }
        
        return dummyHead->next;
    }
};