本文共 2819 字，大约阅读时间需要 9 分钟。

方法一：时间优先 建立一个hash_set，key为链表中已经遍历的节点内容，开始时为空。 从头开始遍历链表中的节点： - 如果节点内容已经在hash_set中存在，则删除此节点，继续向后遍历； - 如果节点内容不在hash_set中，则保留此节点，将节点内容添加到hash_set中，继续向后遍历。 这里STL没有hash_set，我直接用set实现的： 方法二：空间优先 解决的思路如下： 建立指针p，用于遍历链表； 建立指针q，q遍历p后面的结点，并与p数值比较；

建立指针r，r保存需要删掉的结点，再把需要删掉的结点的前后结点相接。由此去掉重复值。

下面是相关代码：

#include "list.h"#include 
   
    using namespace std;//借助STL中的set来删除链表中的重复项，比较高效（时间比中间更重要）//建立STL中的set，key为链表中已经遍历的结点内容，开始时为空//从头开始遍历链表中的结点：//如果结点内容已经在set中存在，则删除此结点，继续向后遍历//如果结点内容不在set中，则保留此结点，将结点内容添加到set中，继续向后遍历ListNode* del_repeated_nodes(ListNode* pHead){    if(pHead == NULL)        return pHead;    set
    
      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;            }else                pIterNode = 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;}
    
   

转载地址：http://izcoi.baihongyu.com/