欢迎大家访问我的博客Tony’s Blog，一起站在巨人的肩膀上！
题目描述：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
算法描述：
这道题我是用循环遍历链表的方法来做的。
- 设置一个新的头结点，放到第一位，以免遇到前两位或者前三位，前四位…….结点相等的情况
- 创建三个指针pre,cur和lat，分别指向当前结点的前一个结点、当前结点、当前结点的后一个结点；
- 以cur结点为主要结点，while遍历整个链表
- 以lat为工作结点，if中判断cur与lat的值是否相等
- 返回新的头结点的下一个结点
代码：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
int i,j;
//注意代码鲁棒性，当头结点为空时的情况
if(pHead==NULL)
{
return NULL;
}
//注意代码鲁棒性，当只有一个头结点的情况
if(pHead!=NULL&&pHead->next==NULL)
{
return pHead;
}
//创建一个新的头结点，放到第一位，以免遇到前两位或者前三位，前四位.......结点相等的情况
ListNode *newHead=new ListNode(-1);
newHead->next=pHead;
//创建三个指针pre,cur和lat，分别指向当前结点的前一个结点、当前结点、当前结点的后一个结点；
ListNode *pre=newHead;
ListNode *cur=pHead;
ListNode *lat=NULL;
//以cur结点为主要结点，while遍历整个链表
while(cur!=NULL&&cur->next!=NULL)
{
lat=cur->next;//后一个结点
//以lat为工作结点，if中判断cur与lat的值相等
if(cur->val==lat->val)
{
//由于相等的结点未必只有一个，这里让工作结点lat循环到相等结点的末尾
while(lat&&lat->val==cur->val)
{
lat=lat->next;
}
//注意这题是要删除重复的结点，相等的结点一个都不保留
//因此指针指向两个值不相等的结点
pre->next=lat;
cur=lat;
}
//以lat为工作结点，if中判断cur与lat的值不相等，则cur,pre两个结点都往后一位，继续判断
else
{
cur=cur->next;
pre=pre->next;
}
}
//注意这里的返回值，返回头结点的下一个结点
return newHead->next;
}
};
注意点：
- 注意要增加一个头结点，放到第一位，以免遇到前两位或者前三位，前四位…….结点相等的情况
- 这题是要删除重复的结点，因此重复的结点一个都不保留
- 这题是排好序的链表，因此重复的结点一定都在一块，由于重复的结点未必只有一个，因此这里让工作结点lat循环到相等结点的末尾
- 这里这里指针调整指向就相当于做了删除链表结点的操作
- 注意返回值，返回头结点的下一个结点
引申
如果这题没说排好序的链表这一前提条件，也就意味着重复的结点不一定团在一块，用map统计各个结点数值出现的次数，再遍历链表就好了
