<span>排序链表去重</span>

1、排序链表去重（保留一个）：

给定一个排序链表，删除重复元素，只保留重复元素中第一次出现的结点。

如：给定：3->4->5->6->6->6->7->8->8->9->10

返回：3->4->5->6->7->8->9->10

程序实现：

 1 /************************************
 2 File Name:DeleteDuplicateNode.cpp
 3 Author: godfrey
 4 Created Time: 2016/04/29
 5 *************************************/
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 using namespace std;
10 
11 typedef struct tagSNode{
12     int value;
13     tagSNode* pNext;
14 
15     tagSNode(int v):value(v),pNext(NULL) {}
16 }SNode;
17 //打印链表
18 void Print(SNode* pHead){
19     SNode* p = pHead->pNext;
20     while(p){
21         cout<<p->value<<" ";
22         p = p->pNext;
23     }
24     cout<<endl;
25 }
26 //删除分配结点空间
27 void Destroy(SNode* pHead){
28     SNode* p;
29     while(pHead){
30         p = pHead->pNext;
31         delete pHead;
32         pHead = p;
33     }
34 }
35 //排序链表去重，重复元素保留第一次出现的元素
36 void DeleteDuplicateNode(SNode* pHead){
37     SNode* pPre = pHead->pNext;
38     SNode* pCur = NULL;
39     while(pPre){
40         pCur = pPre->pNext;
41         if(pCur && (pPre->value == pCur->value)){
42             pPre->pNext = pCur->pNext;
43             delete pCur;
44         }
45         else{
46             pPre = pCur;
47         }
48     }
49 }
50 int main()
51 {
52     SNode* pHead = new SNode(0);
53     int data[] = {3,4,5,6,6,6,7,8,8,9,10};
54     int size = sizeof(data)/sizeof(int);
55     for(int i=size-1;i>=0;i--){
56         SNode* p = new SNode(data[i]);
57         p->pNext = pHead->pNext;
58         pHead->pNext = p;
59     }
60 
61     Print(pHead);
62     DeleteDuplicateNode(pHead);
63     Print(pHead);
64     Destroy(pHead);
65     return 0;
66 }

当然，同样的想法可以换一种编码形式，再额外使用一个结点：

 1 //排序链表去重2，重复元素保留第一次出现的结点
 2 void DeleteDuplicateNode2(SNode* pHead){
 3     SNode* pPre = pHead;
 4     SNode* pCur = pHead->pNext;
 5     SNode* t = NULL;
 6     while(pCur){
 7         t = pCur->pNext;
 8         while(t && (pCur->value == t->value)){
 9             pPre->pNext = t;
10             delete pCur;
11             pCur = t;
12             t = pCur->pNext;
13         }
14         pPre = pCur;
15         pCur = t;
16     }
17 }

两者运行结果相同，其为：

2、排序链表去重（全部删除）：

若题目变成，发现重复元素，则重复元素全部删除。

代码实现：

 1 //排序链表去重3，删除所有的重复元素
 2 void DeleteDuplicateNode3(SNode* pHead){
 3     SNode* pPre = pHead;
 4     SNode* pCur = pHead->pNext;
 5     SNode* t = NULL;
 6     bool bDup;//重复标志位
 7     while(pCur){
 8         t = pCur->pNext;
 9         bDup = false;
10         while(t && (pCur->value == t->value)){
11             pPre->pNext = t;
12             delete pCur;
13             pCur = t;
14             t = pCur->pNext;
15             bDup = true;
16         }
17         if(bDup){//pCur与原数据重复
18             pPre->pNext = t;
19             delete pCur;
20         }
21         else{//pCur没有重复，进行后移
22             pPre = pCur;
23         }
24         pCur = t;
25     }
26 }