Day4-线性表-排序链表去重
一 老规矩
昨天口误了，链表之后，还有线性表的队列和栈，并不是字符串，惊不惊喜意不意外
然后今天是最后一篇初级链表，然后，今天只有一篇，但是有两个问题，惊不惊喜意不意外
二 题目
Q：给定排序的链表，删除重复元素，只保留重复元素第一次出现的节点
那么对于以下这个链表
2→3→3→5→7→8→8→8→9→9→10
则返回
2→3→5→7→8→9→10
三 分析
排序链表，意味着，重复元素都是相邻的，即你前面删完的重复元素，后面不会出现~
这第一种情况比较好理解，用两个指针，pre和cur，cur指向当前节点，pre指向前驱节点。当发现节点值一样时，直接把当前节点的后继，cur→next这个指向，赋值给前驱节点的后继，即实现“删除了当前节点”。
四 完整代码
//
// Created by renyi on 2019-06-01.
//
#include <iostream>
using namespace std;
struct Node{
int value;
Node* next;
Node(int v):value(v),next(NULL){}
};
Node* deleteDuplicateNode(Node* head){
Node* pre = head;//初始化前驱指针
Node* cur;//初始化当前指针
while(pre){
cur = pre->next;
if (cur && (cur->value == pre->value)){
pre->next = cur->next;//若发现重复，则将前驱指针pre的后继，赋值为当前指针cur的后继
} else{
pre = cur;
}
}
return head;
}
Node* deleteAllDuplicateNode(Node* head){
Node* pre = head;
Node* cur = pre->next;
Node* next;
bool dup;
while(cur){
next = cur->next;
dup = false;
while(next && cur->value == next->value){
pre->next = next;
cur = next;
next = cur->next;
dup = true;
}
if (dup){
pre->next = next;
} else{
pre = cur;
}
cur = next;
}
return head;
}
void print(Node* head){
while(head){
if (head->next){
cout<<head->value<<"->";
} else{
cout<<head->value;
}
head = head->next;
}
cout<<endl;
}
int main(){
Node a(2);
Node b(3);
Node c(3);
Node d(5);
Node e(7);
Node f(8);
Node g(8);
Node h(8);
Node i(9);
Node j(9);
Node k(10);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
f.next = &g;
g.next = &h;
h.next = &i;
i.next = &j;
j.next = &k;
Node* head = deleteDuplicateNode(&a);
//Node* head = deleteAllDuplicateNode(&a);
print(head);
return 0;
}
返回
五 升级版-发现重复元素，则重复元素全部删除，该怎么改呢？
即返回
2→5→7→10
冷静分析：
第一种情况比较好实现，因为发现值一样，删除就完事了。
那第二种情况复杂在哪？
重复的元素，全删，不保留。那我怎么知道这个元素是不是重复的呢？
很明显，我们想到了：用一个变量，来标志当前节点元素是不是重复的。
0，1，这样标志也行，我采用了布尔变量。
即，一个节点的值是重复的，那么它的布尔值dup就为true，它在最后也会被删掉，不保留。
需要特别注意的是：
在对重复节点处理时
比如 2→3→3
第一种情况的处理：删后面的3，留第一个3
第二种情况的处理：从前面开始删，删前面的3，最后一个3在判断布尔值为true的时候删掉。
两个函数都附在上面的代码中了
还请大家仔细阅读代码，动手尝试，画节点图~
返回
六 总结
初级链表问题就到这啦~然后从明天开始，对线性表-队列，栈的算法题进行共同探讨嘛～
