在O(1)时间删除链表结点

需要考虑的有

1)删除的结点位于链表尾部

2)链表只有一个结点(删除的是头结点也是尾结点)

常规思维

直接删除这个结点本身

创新思维

可以把下一个结点的内容复制出来覆盖被删除的结点 然后把下一个结点删除

// 题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该// 结点。#include <cstdio>#include "..\Utilities\List.h"void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted){    if(!pListHead || !pToBeDeleted)        return;    // 要删除的结点不是尾结点    if(pToBeDeleted->m_pNext != nullptr)    {        ListNode* pNext = pToBeDeleted->m_pNext;        pToBeDeleted->m_nValue = pNext->m_nValue;        pToBeDeleted->m_pNext = pNext->m_pNext;         delete pNext;        pNext = nullptr;    }    // 链表只有一个结点，删除头结点（也是尾结点）    else if(*pListHead == pToBeDeleted)    {        delete pToBeDeleted;        pToBeDeleted = nullptr;        *pListHead = nullptr;    }    // 链表中有多个结点，删除尾结点    else    {        ListNode* pNode = *pListHead;        while(pNode->m_pNext != pToBeDeleted)        {            pNode = pNode->m_pNext;                    }         pNode->m_pNext = nullptr;        delete pToBeDeleted;        pToBeDeleted = nullptr;    }}// ====================测试代码====================void Test(ListNode* pListHead, ListNode* pNode){    printf("The original list is: \n");    PrintList(pListHead);    printf("The node to be deleted is: \n");    PrintListNode(pNode);    DeleteNode(&pListHead, pNode);        printf("The result list is: \n");    PrintList(pListHead);}// 链表中有多个结点，删除中间的结点void Test1(){    ListNode* pNode1 = CreateListNode(1);    ListNode* pNode2 = CreateListNode(2);    ListNode* pNode3 = CreateListNode(3);    ListNode* pNode4 = CreateListNode(4);    ListNode* pNode5 = CreateListNode(5);    ConnectListNodes(pNode1, pNode2);    ConnectListNodes(pNode2, pNode3);    ConnectListNodes(pNode3, pNode4);    ConnectListNodes(pNode4, pNode5);    Test(pNode1, pNode3);    DestroyList(pNode1);}// 链表中有多个结点，删除尾结点void Test2(){    ListNode* pNode1 = CreateListNode(1);    ListNode* pNode2 = CreateListNode(2);    ListNode* pNode3 = CreateListNode(3);    ListNode* pNode4 = CreateListNode(4);    ListNode* pNode5 = CreateListNode(5);    ConnectListNodes(pNode1, pNode2);    ConnectListNodes(pNode2, pNode3);    ConnectListNodes(pNode3, pNode4);    ConnectListNodes(pNode4, pNode5);    Test(pNode1, pNode5);    DestroyList(pNode1);}// 链表中有多个结点，删除头结点void Test3(){    ListNode* pNode1 = CreateListNode(1);    ListNode* pNode2 = CreateListNode(2);    ListNode* pNode3 = CreateListNode(3);    ListNode* pNode4 = CreateListNode(4);    ListNode* pNode5 = CreateListNode(5);    ConnectListNodes(pNode1, pNode2);    ConnectListNodes(pNode2, pNode3);    ConnectListNodes(pNode3, pNode4);    ConnectListNodes(pNode4, pNode5);    Test(pNode1, pNode1);    DestroyList(pNode1);}// 链表中只有一个结点，删除头结点void Test4(){    ListNode* pNode1 = CreateListNode(1);    Test(pNode1, pNode1);}// 链表为空void Test5(){    Test(nullptr, nullptr);}int main(int argc, char* argv[]){    Test1();    Test2();    Test3();    Test4();    Test5();    return 0;}

删除重复结点

思路:确定删除函数的参数,这个函数需要输入待删除链表的头结点.头结点可能与后面的结点重复.头结点也有可能被删除

需要考虑的

1)只有几个结点是重复的

2)没有重复的

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

4)所有结点的值都相同

5)所有结点都成对出现

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

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

8)空链表

// 面试题18（二）：删除链表中重复的结点// 题目：在一个排序的链表中，如何删除重复的结点？例如，在图3.4（a）中重复// 结点被删除之后，链表如图3.4（b）所示。#include <cstdio>#include "../Utilities/list.h"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(char* testName, ListNode** pHead, int* expectedValues, int expectedLength){    if(testName != nullptr)        printf("%s begins: ", testName);    DeleteDuplication(pHead);    int index = 0;    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(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, 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[] = { 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;    Test("Test4", &pHead, nullptr, 0);    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;    Test("Test5", &pHead, nullptr, 0);    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[] = { 2, 4 };    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);    ConnectListNodes(pNode1, nullptr);    ListNode* pHead = pNode1;    int expectedValues[] = { 1 };    Test("Test8", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));    DestroyList(pHead);}// 结点中只有两个重复的结点void Test9(){    ListNode* pNode1 = CreateListNode(1);    ListNode* pNode2 = CreateListNode(1);    ConnectListNodes(pNode1, pNode2);    ListNode* pHead = pNode1;    Test("Test9", &pHead, nullptr, 0);    DestroyList(pHead);}// 空链表void Test10(){    ListNode* pHead = nullptr;    Test("Test10", &pHead, nullptr, 0);}int main(int argc, char* argv[]){    Test1();    Test2();    Test3();    Test4();    Test5();    Test6();    Test7();    Test8();    Test9();    Test10();    return 0;}