删除单链表中的重复节点(c语言版本)

心已赠人 2022-03-02 11:40 187阅读 0赞

这是一道经典的面试题，下面是我的研究和举一反三，特整理如下：

分为三种情形:

（1）删除有序链表的重复节点，重复节点一个都不留

（2）删除有序链表的重复节点，重复节点只留一个

（3）删除无序链表的重复节点，重复节点只留一个

下面是相关节点的定义：

typedef struct ListNode {
        int val;
        struct ListNode *next;                                                      
    } ListNode;
    
    ListNode* CreateListNode(int value){
        ListNode* pNode = (ListNode*)malloc(sizeof(ListNode));
        if(pNode == NULL){
            printf("failed to create ListNode\n");
            exit(-1);
        }   
           
        pNode->val = value;
        pNode->next = NULL;
        return pNode;
    }      
           
    void ConnectListNodes(ListNode* pCurrent, ListNode* pNext){
        if(pCurrent == NULL || pNext == NULL){
            printf("Error to connect two nodes\n");
            exit(-1);
        }   
           
        pCurrent->next = pNext;
    }      
           
    void DestroyListNode(ListNode* pNode){
        if(pNode != NULL){
            printf("-----delete list node [%d]-----\n", pNode->val);
            free(pNode);
        }   
    }

下面给出解读：

1）下面的代码针对删除有序单链表的重复节点，重复节点都删除。

ListNode* DeleteDuplication(ListNode* pHead){
        if(pHead == NULL)
            return NULL;
     
        //指向当前节点前最晚访问过的不重复节点；                                    
        ListNode* pPre = NULL;
        //指向当前正在处理的节点；
        ListNode* pCur = pHead;
        //指向当前节点后面的值相同的节点；
        ListNode* pNext = NULL;
        //临时存放节点
        ListNode* pNode = NULL;
     
        while(pCur != NULL){
            //下一个节点与当前节点相同
            if(pCur->next != NULL && pCur->next->val == pCur->val){
                pNext = pCur->next;
                //找出所有与当前节点值相同的节点，因为是排序过的链表，它们都在一切
                while(pNext != NULL && pNext->val == pCur->val){
                    pNode = pNext->next;
                    DestroyListNode(pNext);
                    pNext = pNode;
                }   
                //现在要删除pCur->...->pNext->之间的所有节点
                //如果pCur是链表头，要更新链表头的位置
                if(pCur == pHead)
                    pHead = pNext;
                else
                    pPre->next = pNext;
                DestroyListNode(pCur);
                pCur = pNext;
            }else{
                pPre = pCur;
                pCur = pCur->next;
            }   
        }   
     
        return pHead;
    }

2）下面是有序链表，只留一个的

//删除有序链表中的重复节点，仅保留一个，使用2指针定位
    //考虑到这里需要用到测试框架，这里必须使用二级指针
    ListNode* DeleteDuplication(ListNode** pHead){
        if(pHead == NULL || *pHead == NULL)                                         
            return NULL;
                
        //指向当前正在处理的节点；
        ListNode* pCur = *pHead;
        //指向当前节点后面的值相同的节点；
        ListNode* pNext = NULL;
        //临时存放节点
        ListNode* pNode = NULL;
                
        while(pCur != NULL){
            //下一个节点与当前节点相同
            if(pCur->next != NULL && pCur->next->val == pCur->val){
                pNext = pCur->next;
                //找出所有与当前节点值相同的节点，因为是排序过的链表，它们都在一切
                while(pNext != NULL && pNext->val == pCur->val){
                    pNode = pNext->next;
                    DestroyListNode(pNext);
                    pNext = pNode;
                }   
                //将当前节点指向后续不同值的首个节点
                pCur->next = pNext;
            }   
            pCur = pCur->next;
        }       
             
        return *pHead;
    }

3）下面是无序链表，只留一个的(注意：这里会兼容前面的两种情况)

//删除无序链表中的重复节点，仅保留一个，使用2指针定位                           
    //考虑到这里需要用到测试框架，这里必须使用二级指针
    ListNode* DeleteDuplication(ListNode** pHead){
        if(pHead == NULL || *pHead == NULL)
            return NULL; 
                         
        //指向当前正在处理的节点；
        ListNode* p = *pHead;
        //用于遍历p之后的节点；
        ListNode* q = NULL;
        ListNode* r = NULL;
                         
        while(p != NULL){
            q = p;       
            //若后面有节点与当前节点相同，将其统统删除
            while(q->next != NULL){
                if(q->next->val == p->val){
                    //保存需要删掉的节点
                    r = q->next;
                    //需要删掉的节点的前后节点相接
                    q->next = r->next;
                    DestroyListNode(r);
                }        
                else{    
                    q = q->next;
                }        
            }            
            p = p->next; 
        }                
                         
        return *pHead;   
    }

下面是针对第三种情况编写的用户测试的截图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhb182Mjc_size_16_color_FFFFFF_t_70][]

下面是我针对第三种情况的源码实现：

//description: 描述删除单链表的重复节点
    //date: 2019-03-20
    
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    
    typedef struct ListNode {
        int val;
        struct ListNode *next;
    } ListNode;
    
    
    ListNode* CreateListNode(int value){
        ListNode* pNode = (ListNode*)malloc(sizeof(ListNode));
        if(pNode == NULL){
            printf("failed to create ListNode\n");
            exit(-1);
        }
    
        pNode->val = value;
        pNode->next = NULL;
        return pNode;
    }
    
    void ConnectListNodes(ListNode* pCurrent, ListNode* pNext){
        if(pCurrent == NULL || pNext == NULL){
            printf("No necessary to connect two nodes\n");
            return;
        }
    
        pCurrent->next = pNext;
    }
    
    void DestroyListNode(ListNode* pNode){
        if(pNode != NULL){
            printf("-----delete list node [%d]-----\n", pNode->val);
            free(pNode);
        }
    }
    
    //在表头节点后面拼接n个随机元素的单链表
    void CreateList(ListNode **pHead, int n){
        if(pHead == NULL || *pHead == NULL){
            printf("Invalid List header ptr\n");
            exit(-1);
        }
    
        int i;
        srand(time(0));
        ListNode *pNew, *pNode = *pHead;
        for(i=0; i<n; i++){
            pNew = (ListNode*)malloc(sizeof(ListNode));
            pNew->val = rand()%100 + 1;
            pNode->next = pNew;
    
            pNode = pNew;
        }
        pNode->next = NULL;
    }
    
    void DestroyList(ListNode* pHead){
        ListNode *pNode = pHead;
        while(pNode != NULL){
            pHead = pNode->next;
            free(pNode);
            pNode = pHead;
        }
    }
    
    void PrintList(ListNode* pHead){
        printf("------------print list begin-----------");
        ListNode* pNode = pHead;
        while(pNode != NULL){
            printf("%d ", pNode->val);
            pNode = pNode->next;
        }
        printf("------------print list end-------------");
    }
    
    //==================业务函数定义到这里=============
    
    
    //删除无序链表中的重复节点，仅保留一个，使用2指针定位
    //考虑到这里需要用到测试框架，这里必须使用二级指针
    ListNode* DeleteDuplication(ListNode** pHead){
        if(pHead == NULL || *pHead == NULL)
            return NULL;
    
        //指向当前正在处理的节点；
        ListNode* p = *pHead;
        //用于遍历p之后的节点；
        ListNode* q = NULL;
        ListNode* r = NULL;
    
        while(p != NULL){
            q = p;
            //若后面有节点与当前节点相同，将其统统删除
            while(q->next != NULL){
                if(q->next->val == p->val){
                    //保存需要删掉的节点
                    r = q->next;
                    //需要删掉的节点的前后节点相接
                    q->next = r->next;
                    DestroyListNode(r);
                }
                else{
                    q = q->next;
                }
            }
            p = p->next;
        }
    
        return *pHead;
    }
    
    //==================测试代码=======================
    void Test(char* testName, ListNode** pHead, int* expectedValues, int expectedLength){
        if(testName != NULL)
            printf("%s begins:\n", testName);
    
        //======真正要干的活儿==========
        ListNode* pNode = DeleteDuplication(pHead);
    
        int idx = 0;
        while(pNode !=NULL && idx < expectedLength){
            if(pNode->val != expectedValues[idx])
                break;
    
            pNode = pNode->next;
            idx++;
        }
    
        if(pNode == NULL && idx == expectedLength)
            printf("%s Passed.\n", testName);
        else
            printf("%s FAILED.\n", testName);
    }
    
    //--------------下面测试一些特例情况--------------
    
    //某些节点是重复的
    void Test1(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(1);
        ListNode* pNode2 = CreateListNode(2);
        ListNode* pNode3 = CreateListNode(3);
        ListNode* pNode4 = CreateListNode(3);
        ListNode* pNode5 = CreateListNode(4);
        ListNode* pNode6 = CreateListNode(4);
        ListNode* pNode7 = CreateListNode(5);
    
        ConnectListNodes(pNode1, pNode2);
        ConnectListNodes(pNode2, pNode3);
        ConnectListNodes(pNode3, pNode4);
        ConnectListNodes(pNode4, pNode5);
        ConnectListNodes(pNode5, pNode6);
        ConnectListNodes(pNode6, pNode7);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {1, 2, 3, 4, 5};
        Test("Test1", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    //没有节点重复
    void Test2(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(1);
        ListNode* pNode2 = CreateListNode(2);
        ListNode* pNode3 = CreateListNode(3);
        ListNode* pNode4 = CreateListNode(4);
        ListNode* pNode5 = CreateListNode(5);
        ListNode* pNode6 = CreateListNode(6);
        ListNode* pNode7 = CreateListNode(7);
    
        ConnectListNodes(pNode1, pNode2);
        ConnectListNodes(pNode2, pNode3);
        ConnectListNodes(pNode3, pNode4);
        ConnectListNodes(pNode4, pNode5);
        ConnectListNodes(pNode5, pNode6);
        ConnectListNodes(pNode6, pNode7);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {1, 2, 3, 4, 5, 6, 7};
        Test("Test2", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    //除了一个节点之外其它所有节点的值都相同
    void Test3(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(1);
        ListNode* pNode2 = CreateListNode(1);
        ListNode* pNode3 = CreateListNode(1);
        ListNode* pNode4 = CreateListNode(1);
        ListNode* pNode5 = CreateListNode(1);
        ListNode* pNode6 = CreateListNode(1);
        ListNode* pNode7 = CreateListNode(2);
    
        ConnectListNodes(pNode1, pNode2);
        ConnectListNodes(pNode2, pNode3);
        ConnectListNodes(pNode3, pNode4);
        ConnectListNodes(pNode4, pNode5);
        ConnectListNodes(pNode5, pNode6);
        ConnectListNodes(pNode6, pNode7);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {1, 2};
        Test("Test3", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    //所有节点的值都是相同的
    void Test4(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(1);
        ListNode* pNode2 = CreateListNode(1);
        ListNode* pNode3 = CreateListNode(1);
        ListNode* pNode4 = CreateListNode(1);
        ListNode* pNode5 = CreateListNode(1);
        ListNode* pNode6 = CreateListNode(1);
        ListNode* pNode7 = CreateListNode(1);
    
        ConnectListNodes(pNode1, pNode2);
        ConnectListNodes(pNode2, pNode3);
        ConnectListNodes(pNode3, pNode4);
        ConnectListNodes(pNode4, pNode5);
        ConnectListNodes(pNode5, pNode6);
        ConnectListNodes(pNode6, pNode7);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {1};
        Test("Test4", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    //所有节点都成对出现
    void Test5(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(1);
        ListNode* pNode2 = CreateListNode(1);
        ListNode* pNode3 = CreateListNode(2);
        ListNode* pNode4 = CreateListNode(2);
        ListNode* pNode5 = CreateListNode(3);
        ListNode* pNode6 = CreateListNode(3);
        ListNode* pNode7 = CreateListNode(4);
        ListNode* pNode8 = CreateListNode(4);
    
        ConnectListNodes(pNode1, pNode2);
        ConnectListNodes(pNode2, pNode3);
        ConnectListNodes(pNode3, pNode4);
        ConnectListNodes(pNode4, pNode5);
        ConnectListNodes(pNode5, pNode6);
        ConnectListNodes(pNode6, pNode7);
        ConnectListNodes(pNode7, pNode8);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {1, 2, 3, 4};
        Test("Test5", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    
    //除了两个节点之外其它所有节点都成对出现
    void Test6(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(1);
        ListNode* pNode2 = CreateListNode(1);
        ListNode* pNode3 = CreateListNode(2);
        ListNode* pNode4 = CreateListNode(3);
        ListNode* pNode5 = CreateListNode(3);
        ListNode* pNode6 = CreateListNode(4);
        ListNode* pNode7 = CreateListNode(5);
        ListNode* pNode8 = CreateListNode(5);
    
        ConnectListNodes(pNode1, pNode2);
        ConnectListNodes(pNode2, pNode3);
        ConnectListNodes(pNode3, pNode4);
        ConnectListNodes(pNode4, pNode5);
        ConnectListNodes(pNode5, pNode6);
        ConnectListNodes(pNode6, pNode7);
        ConnectListNodes(pNode7, pNode8);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {1, 2, 3, 4, 5};
        Test("Test6", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    //链表中只有两个不重复的节点
    void Test7(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(1);
        ListNode* pNode2 = CreateListNode(2);
    
        ConnectListNodes(pNode1, pNode2);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {1, 2};
        Test("Test7", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    //链表中只有两个重复的节点
    void Test8(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(1);
        ListNode* pNode2 = CreateListNode(1);
    
        ConnectListNodes(pNode1, pNode2);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {1};
        Test("Test8", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    //无序链表中某些节点是重复的
    void Test9(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(11);
        ListNode* pNode2 = CreateListNode(2);
        ListNode* pNode3 = CreateListNode(3);
        ListNode* pNode4 = CreateListNode(3);
        ListNode* pNode5 = CreateListNode(9);
        ListNode* pNode6 = CreateListNode(4);
        ListNode* pNode7 = CreateListNode(5);
        ListNode* pNode8 = CreateListNode(5);
        ListNode* pNode9 = CreateListNode(3);
    
        ConnectListNodes(pNode1, pNode2);
        ConnectListNodes(pNode2, pNode3);
        ConnectListNodes(pNode3, pNode4);
        ConnectListNodes(pNode4, pNode5);
        ConnectListNodes(pNode5, pNode6);
        ConnectListNodes(pNode6, pNode7);
        ConnectListNodes(pNode7, pNode8);
        ConnectListNodes(pNode8, pNode9);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {11, 2, 3, 9, 4, 5};
        Test("Test9", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    //链表中只有一个节点
    void Test10(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(1);
    
        ConnectListNodes(pNode1, NULL);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {1};
        Test("Test10", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    //空链表
    void Test11(){
        ListNode* pHead = NULL;
    
        Test("Test11", &pHead, NULL, 0);
    }
    
    int main(int argc, char** argv){
        Test1();
        Test2();
        Test3();
        Test4();
        Test5();
        Test6();
        Test7();
        Test8();
        Test9();
        Test10();
        Test11();
    
        return 0;
    }

参考文献

\[1\].《剑指Offer名企面试官精讲典型编程题》第2版 面试题18-2

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhb182Mjc_size_16_color_FFFFFF_t_70]: /images/20220302/a1f90f184cec44e587a8564752f22871.png