题目描述

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

思路

关键点：创建一个指针last，如果是重复元素，则使last指向重复节点中的最后一个；如果不是，就指向当前节点
创建一个pre指针，这个指针是结果链表的当前指针
另外一个需要注意的是：pre不能一开始就等于pHead，因为这个时候还不确定第一个节点是否是重复节点，这里看到讨论区的一个思路就是再创建一个自己的头结点，它的next指向原链表的头结点，这样就需要先判断头结点是不是重复节点再决定要不要添加到结果链表中去，最后返回的时候返回它的next

代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead==NULL||pHead->next==NULL)
            return pHead;
        //创建一个新节点
        ListNode* newHead=new ListNode(0);
        newHead->next=pHead;
        ListNode* pre=newHead;
        ListNode* last=newHead->next;
        while(last!=NULL)
        {
            if(last->next!=NULL&&last->val==last->next->val)
            {
                while(last->next!=NULL&&last->val==last->next->val)
                {
                    last=last->next;
                }
                pre->next=last->next;
                last=pre->next;
            }
            else
            {
                pre->next=last;
                pre=pre->next;//直到确定这个数不是重复元素才把它加入到结果链表中去
                last=last->next;
            }
        }
        return newHead->next;
    }
};