题目描述：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
数据范围：链表长度满足 1<=n<=1000 ，链表中的值满足 1<=nval<=1000
进阶：空间复杂度O(n) ，时间复杂度 O(n)
例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：
示例：
输入：
{1,2,3,3,4,4,5}
返回值：
{1,2,5}
解题思路：
本题考察数据结构链表的使用。本题常用两种解法。
- set遍历法。第一遍遍历用set存储重复的值，第二遍遍历将重复的值对应的结点删掉。该方法的好处是即使链表未排序，也能使用。
- 直接删除法。首先建立哨兵vhead，定义pre和cur前后指针进行遍历；遍历过程中如果出现前后重复的情况，则将cur连接到下一个非重复的结点，并重新将pre与其连接；若前后未重复，则前后指针同步向后进行；一次遍历完成后，重复的结点已删除。该方法适合已经排序的链表。
测试代码：
解法一：set遍历法
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { if(!pHead) return pHead; set<int> s; ListNode *pre=pHead; ListNode *cur=pHead->next; // 第一遍遍历把重复的数值放入set while(cur) { if(pre->val==cur->val) { s.insert(pre->val); } pre=pre->next; cur=cur->next; } ListNode *vhead=new ListNode(-1); vhead->next=pHead; pre=vhead; cur=pHead; // 第一遍遍历把重复数值对应的结点删除 while(cur) { if(s.count(cur->val)) { cur=cur->next; pre->next=cur; } else{ pre=pre->next; cur=cur->next; } } return vhead->next; } };
解法二：直接删除法
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { if(!pHead) return pHead; ListNode *vhead=new ListNode(-1); vhead->next=pHead; ListNode *pre=vhead; ListNode *cur=pHead; // 遍历删除重复结点 while(cur) { // 如果有重复结点 if(cur->next && cur->val==cur->next->val) { cur=cur->next; // 若有连续重复的情况，将cur指向最后一次出现重复的结点 while(cur->next && cur->val==cur->next->val) { cur=cur->next; } // 连接下一个非重复的结点 cur=cur->next; pre->next=cur; } // 若无重复结点，同步指向下一个 else{ pre=pre->next; cur=cur->next; } } return vhead->next; } };
