声明: 本总结仅为个人学习总结,以防止遗忘而作,不得转载和商用。
题目:给定排序的链表,删除重复元素,只保留重复元素第一次出现的结点.
如:
给定: 2->3->3->5->7->8->8->8->9->9->10
返回: 2->3->5->7->8->9->10
问题分析:
若p->next的值和p的值相等,则将p->next->next赋值给p,删除p->next;重复上述过程,直至链表尾端
Java版本的实现一:
public static void deleteDuplicateNode(Node pHead){
Node pPre = pHead.next;
Node pCur;
while(pPre != null){
pCur = pPre.next;
if (pCur != null && pCur.value == pPre.value) {
pPre.next = pCur.next;
}else {
pPre = pCur;
}
}
}
实现二:
public static void deleteDuplicateNode2(Node pHead){
Node pPre = pHead;
Node pCur = pPre.next;
Node pNext;
while(pCur != null){
pNext = pCur.next;
while(pNext != null && pCur.value == pNext.value){
pPre.next = pNext;
pCur = pNext;
pNext = pCur.next;
}
pPre = pCur;
pCur = pNext;
}
}
题目进一步扩展,若发现生重复元素,则重复元素全部删除,
如:
给定: 2->3->3->5->7->8->8->8->9->9->10
返回: 2->5->7->10
Java实现如下:
public static void deleteDuplicateNode3(Node pHead){
Node pPre = pHead;
Node pCur = pPre.next;
Node pNext;
boolean bDup;
while(pCur != null){
pNext = pCur.next;
bDup = false;
while (pNext != null && pCur.value == pNext.value) {
pPre.next = pNext;
pCur = pNext;
pNext = pCur.next;
bDup = true;
}
if (bDup) {//此刻的pCur与原数据重复,删之
pPre.next = pNext;
}else {//pCur未发现重复,则pPre后移
pPre = pCur;
}
pCur = pNext;
}
}
测试结果:
Linked List: 0->2->3->3->5->7->8->8->8->9->9->30->
Linked List: 0->2->5->7->30->