《劍指offer》:[57]刪除鏈表中重復(fù)的結(jié)點(diǎn)
來(lái)源：程序員人生 發(fā)布時(shí)間：2016-08-15 08:56:31 閱讀次數(shù)：2421次
題目：在1個(gè)排序的鏈表中，如何刪除重復(fù)的結(jié)點(diǎn)？
例如，在圖a中重復(fù)結(jié)點(diǎn)被刪除以后，鏈表如圖b所示。
方案：這個(gè)題應(yīng)當(dāng)說(shuō)是比較簡(jiǎn)單的，不在贅述，主要利用3個(gè)指針，就能夠解決這個(gè)問(wèn)題。
具體實(shí)現(xiàn)代碼：
#include <iostream>
using namespace std;
struct ListNode
{
int data;
ListNode *next;
};
ListNode *pHead=NULL;
ListNode *pEnd=NULL;
void CreateList()
{
int data;
cin>>data;
while(0!=data)
{
ListNode *pNode=new ListNode;
pNode->data=data;
pNode->next=NULL;
if(pHead==NULL)//空鏈表
{
pHead=pNode;
pEnd=pNode;
}
else//非空鏈表；
{
// 插入在頭結(jié)點(diǎn)；
if(pHead->data > data )
{
pNode->next=pHead;
pHead=pNode;
}
// 插入位置在非頭結(jié)點(diǎn)；
else
{
ListNode *p=pHead;
while(p->next&& p->data<data)
p=p->next;
pNode->next=p->next;
p->next=pNode;
}
}
cin>>data;
}
}
void DeleteDuplication(ListNode **head)//必須**，由于有可能刪除頭結(jié)點(diǎn)；
{
if(head==NULL || *head==NULL)
return ;
ListNode *preNode=NULL;
ListNode *pNode=*head;
while(pNode!=NULL)
{
ListNode *pNext=pNode->next;
bool needdelete=false;
if(pNext!=NULL && pNext->data==pNode->data)
needdelete=true;
if(!needdelete)
{
preNode=pNode;
pNode=pNode->next;
}
else
{
int data=pNode->data;//記錄下要?jiǎng)h除的值；
ListNode *tobedel=pNode;
while(tobedel!=NULL && tobedel->data==data)
{
pNext=tobedel->next;
delete tobedel;
tobedel=NULL;
tobedel=pNext;
}
if(preNode==NULL)
*head=pNext;
else
preNode->next=pNext;
pNode=pNext;
}
}
}
void show(ListNode *head)
{
while(head)
{
cout<<head->data<<" ";
head=head->next;
}
cout<<endl;
}
int main()
{
CreateList();
DeleteDuplication(&pHead);
show(pHead);
system("pause");
return 0;
}
運(yùn)行結(jié)果：
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
