《剑指offer》第十八题（删除链表中重复的结点）

时间：2022-08-25 17:06:13
// 面试题18（二）：删除链表中重复的结点

// 题目：在一个排序的链表中，如何删除重复的结点？例如，在图3.4（a）中重复

// 结点被删除之后，链表如图3.4（b）所示。

#include <iostream>

#include "List.h"

using namespace std;

void DeleteDuplication(ListNode** pHead)//注意有可能删除头结点，所以是**

{

    if (pHead == nullptr || *pHead == nullptr)

        return;

    ListNode* pPreNode = nullptr;//用来存储当前最后一个不删的节点

    ListNode* pNode = *pHead;//用来存储下一个待检测的节点

    while (pNode != nullptr)

    {

        ListNode *pNext = pNode->m_pNext;

        bool needDelete = false;

        if (pNext != nullptr && pNext->m_nValue == pNode->m_nValue)//开始检测是否删除

            needDelete = true;

        if (!needDelete)//不要删除的话就往下走

        {

            pPreNode = pNode;

            pNode = pNode->m_pNext;

        }

        else//要删除的话，看看删几个

        {

            int value = pNode->m_nValue;//记住要删的数

            ListNode* pToBeDel = pNode;

            while (pToBeDel != nullptr && pToBeDel->m_nValue == value)//满足

            {

                pNext = pToBeDel->m_pNext;

                delete pToBeDel;//删

                pToBeDel = nullptr;

                pToBeDel = pNext;

            }

            if (pPreNode == nullptr)//要是一直在删头结点，就把这个给头结点

                *pHead = pNext;

            else

                pPreNode->m_pNext = pNext;

            pNode = pNext;

        }

    }

}

// ====================测试代码====================

void Test(const char* testName, ListNode** pHead, int* expectedValues, int expectedLength)

{

    if (testName != nullptr)

        printf("%s begins: ", testName);

    DeleteDuplication(pHead);

    int index = ;

    ListNode* pNode = *pHead;

    while (pNode != nullptr && index < expectedLength)

    {

        if (pNode->m_nValue != expectedValues[index])

            break;

        pNode = pNode->m_pNext;

        index++;

    }

    if (pNode == nullptr && index == expectedLength)

        printf("Passed.\n");

    else

        printf("FAILED.\n");

}

// 某些结点是重复的

void Test1()

{

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ListNode* pNode6 = CreateListNode();

    ListNode* pNode7 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    ConnectListNodes(pNode5, pNode6);

    ConnectListNodes(pNode6, pNode7);

    ListNode* pHead = pNode1;

    int expectedValues[] = { , ,  };

    Test("Test1", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));

    DestroyList(pHead);

}

// 没有重复的结点

void Test2()

{

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ListNode* pNode6 = CreateListNode();

    ListNode* pNode7 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    ConnectListNodes(pNode5, pNode6);

    ConnectListNodes(pNode6, pNode7);

    ListNode* pHead = pNode1;

    int expectedValues[] = { , , , , , ,  };

    Test("Test2", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));

    DestroyList(pHead);

}

// 除了一个结点之外其他所有结点的值都相同

void Test3()

{

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ListNode* pNode6 = CreateListNode();

    ListNode* pNode7 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    ConnectListNodes(pNode5, pNode6);

    ConnectListNodes(pNode6, pNode7);

    ListNode* pHead = pNode1;

    int expectedValues[] = {  };

    Test("Test3", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));

    DestroyList(pHead);

}

// 所有结点的值都相同

void Test4()

{

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ListNode* pNode6 = CreateListNode();

    ListNode* pNode7 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    ConnectListNodes(pNode5, pNode6);

    ConnectListNodes(pNode6, pNode7);

    ListNode* pHead = pNode1;

    Test("Test4", &pHead, nullptr, );

    DestroyList(pHead);

}

// 所有结点都成对出现

void Test5()

{

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ListNode* pNode6 = CreateListNode();

    ListNode* pNode7 = CreateListNode();

    ListNode* pNode8 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    ConnectListNodes(pNode5, pNode6);

    ConnectListNodes(pNode6, pNode7);

    ConnectListNodes(pNode7, pNode8);

    ListNode* pHead = pNode1;

    Test("Test5", &pHead, nullptr, );

    DestroyList(pHead);

}

// 除了两个结点之外其他结点都成对出现

void Test6()

{

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ListNode* pNode6 = CreateListNode();

    ListNode* pNode7 = CreateListNode();

    ListNode* pNode8 = CreateListNode();

    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[] = { ,  };

    Test("Test6", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));

    DestroyList(pHead);

}

// 链表中只有两个不重复的结点

void Test7()

{

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ListNode* pHead = pNode1;

    int expectedValues[] = { ,  };

    Test("Test7", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));

    DestroyList(pHead);

}

// 结点中只有一个结点

void Test8()

{

    ListNode* pNode1 = CreateListNode();

    ConnectListNodes(pNode1, nullptr);

    ListNode* pHead = pNode1;

    int expectedValues[] = {  };

    Test("Test8", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));

    DestroyList(pHead);

}

// 结点中只有两个重复的结点

void Test9()

{

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ListNode* pHead = pNode1;

    Test("Test9", &pHead, nullptr, );

    DestroyList(pHead);

}

// 空链表

void Test10()

{

    ListNode* pHead = nullptr;

    Test("Test10", &pHead, nullptr, );

}

int main(int argc, char* argv[])

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    Test6();

    Test7();

    Test8();

    Test9();

    Test10();

    system("pause");

    return ;

}

相关文章