方法一：時間優先
建立一個hash_set，key為鏈表中已經遍歷的節點內容，開始時為空。
從頭開始遍歷鏈表中的節點：
- 如果節點內容已經在hash_set中存在，則刪除此節點，繼續向后遍歷；
- 如果節點內容不在hash_set中，則保留此節點，將節點內容添加到hash_set中，繼續向后遍歷。
這里STL沒有hash_set，我直接用set實現的：


方法二：空間優先
解決的思路如下：
建立指針p，用于遍歷鏈表；
建立指針q，q遍歷p后面的結點，并與p數值比較；

建立指針r，r保存需要刪掉的結點，再把需要刪掉的結點的前后結點相接。由此去掉重復值。

下面是相關代碼：

#include "list.h"
#include <set>
using namespace std;//借助STL中的set來刪除鏈表中的重復項，比較高效（時間比中間更重要）
//建立STL中的set，key為鏈表中已經遍歷的結點內容，開始時為空
//從頭開始遍歷鏈表中的結點：
//如果結點內容已經在set中存在，則刪除此結點，繼續向后遍歷
//如果結點內容不在set中，則保留此結點，將結點內容添加到set中，繼續向后遍歷
ListNode* del_repeated_nodes(ListNode* pHead){if(pHead == NULL)return pHead;set<int> KeySet;ListNode* pNewHead = pHead;ListNode* pCurNode = pHead;KeySet.insert(pHead->value);while(pCurNode->next){//已經存在則刪除if(KeySet.count(pCurNode->next->value)){ListNode* pDelNode = pCurNode->next;pCurNode->next = pCurNode->next->next;delete pDelNode;}else{ //不存在則新增KeySet.insert(pCurNode->next->value);pCurNode = pCurNode->next;}}return pNewHead;
}//使用循環遍歷方法：
//1.建立指針pNode，用于遍歷鏈表
//2.建立指針pIterNode，用于遍歷pNode之后的結點，并與pNode的值比較
//3.建立指針pDupNode，保存需要刪除的結點，再把需要刪除的結點的前后結點相接，由此去掉重復值
ListNode* del_duplicate_nodes(ListNode* pHead){ListNode* pNewHead = pHead;ListNode* pNode = pNewHead;while(pNode){//pNode用于遍歷鏈表ListNode* pIterNode = pNode;while(pIterNode->next){//遍歷pNode之后的結點，并與pIterNode的值比較if(pIterNode->next->value == pNode->value){ListNode* pDupNode = pIterNode->next;//保存要刪除的值pIterNode->next = pIterNode->next->next;delete pDupNode;}elsepIterNode = pIterNode->next;}pNode = pNode->next;}return pNewHead;
}ListNode* Test(ListNode* pHead){printf("The original list is: \n");PrintList(pHead);//這里采用兩種方法：前者空間占優，后者時間占優//ListNode* pNewHead = del_duplicate_nodes(pHead);ListNode* pNewHead = del_repeated_nodes(pHead);printf("The del duplicate list is: \n");PrintList(pNewHead);return pNewHead;
}void Test1(){ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(1);ListNode* pNode3 = CreateListNode(2);ListNode* pNode4 = CreateListNode(2);ListNode* pNode5 = CreateListNode(4);ListNode* pNode6 = CreateListNode(1);ConnectListNode(pNode1,pNode2);ConnectListNode(pNode2,pNode3);ConnectListNode(pNode3,pNode4);ConnectListNode(pNode4,pNode5);ConnectListNode(pNode5,pNode6);ListNode* pReverseHead = Test(pNode1);DestroyList(pReverseHead);
}void Test2(){ListNode* pNode1 = CreateListNode(1);ListNode* pReverseHead = Test(pNode1);DestroyList(pReverseHead);
}void Test3(){Test(NULL);
}int main(int argc, char** argv){Test1();Test2();Test3();return 0;
}

總結

以上是生活随笔為你收集整理的删除链表中的重复项的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。