剑指offer——面试题18:删除链表的节点

  1 #include"List.h"
  2 
  3 void DeleteNode(ListNode** pHead,ListNode* pToBeDeleted)
  4 {
  5     if(*pHead==nullptr || pToBeDeleted==nullptr)
  6         return;
  7     if(pToBeDeleted->m_pNext!=nullptr)
  8     {
  9         ListNode* pNext=pToBeDeleted->m_pNext;
 10         pToBeDeleted->m_pNext=pNext->m_pNext;
 11         pToBeDeleted->m_Value=pNext->m_Value;
 12         delete pNext;
 13         pNext=nullptr;
 14     }
 15     else if(pToBeDeleted==*pHead)
 16     {
 17         delete pToBeDeleted;
 18         pToBeDeleted=nullptr;
 19         *pHead=nullptr;
 20     }
 21     else
 22     {
 23         ListNode* pNode=*pHead;
 24         while(pNode->m_pNext!=pToBeDeleted)
 25             pNode=pNode->m_pNext;
 26         pNode->m_pNext=nullptr;
 27         delete pToBeDeleted;
 28         pToBeDeleted=nullptr;
 29     }
 30 }
 31 void Test(ListNode* pListHead, ListNode* pNode)
 32 {
 33     printf("The original list is: 
");
 34     PrintList(pListHead);
 35 
 36     printf("The node to be deleted is: 
");
 37     PrintListNode(pNode);
 38 
 39     DeleteNode(&pListHead, pNode);
 40 
 41     printf("The result list is: 
");
 42     PrintList(pListHead);
 43 }
 44 
 45 // 链表中有多个结点，删除中间的结点
 46 void Test1()
 47 {
 48     ListNode* pNode1 = CreateListNode(1);
 49     ListNode* pNode2 = CreateListNode(2);
 50     ListNode* pNode3 = CreateListNode(3);
 51     ListNode* pNode4 = CreateListNode(4);
 52     ListNode* pNode5 = CreateListNode(5);
 53 
 54     ConnectListNodes(pNode1, pNode2);
 55     ConnectListNodes(pNode2, pNode3);
 56     ConnectListNodes(pNode3, pNode4);
 57     ConnectListNodes(pNode4, pNode5);
 58 
 59     Test(pNode1, pNode3);
 60 
 61     DestroyList(pNode1);
 62 }
 63 
 64 // 链表中有多个结点，删除尾结点
 65 void Test2()
 66 {
 67     ListNode* pNode1 = CreateListNode(1);
 68     ListNode* pNode2 = CreateListNode(2);
 69     ListNode* pNode3 = CreateListNode(3);
 70     ListNode* pNode4 = CreateListNode(4);
 71     ListNode* pNode5 = CreateListNode(5);
 72 
 73     ConnectListNodes(pNode1, pNode2);
 74     ConnectListNodes(pNode2, pNode3);
 75     ConnectListNodes(pNode3, pNode4);
 76     ConnectListNodes(pNode4, pNode5);
 77 
 78     Test(pNode1, pNode5);
 79 
 80     DestroyList(pNode1);
 81 }
 82 
 83 // 链表中有多个结点，删除头结点
 84 void Test3()
 85 {
 86     ListNode* pNode1 = CreateListNode(1);
 87     ListNode* pNode2 = CreateListNode(2);
 88     ListNode* pNode3 = CreateListNode(3);
 89     ListNode* pNode4 = CreateListNode(4);
 90     ListNode* pNode5 = CreateListNode(5);
 91 
 92     ConnectListNodes(pNode1, pNode2);
 93     ConnectListNodes(pNode2, pNode3);
 94     ConnectListNodes(pNode3, pNode4);
 95     ConnectListNodes(pNode4, pNode5);
 96 
 97     Test(pNode1, pNode1);
 98 
 99     DestroyList(pNode1);
100 }
101 
102 // 链表中只有一个结点，删除头结点
103 void Test4()
104 {
105     ListNode* pNode1 = CreateListNode(1);
106 
107     Test(pNode1, pNode1);
108 }
109 
110 // 链表为空
111 void Test5()
112 {
113     Test(nullptr, nullptr);
114 }
115 
116 int main(int argc, char* argv[])
117 {
118     Test1();
119     Test2();
120     Test3();
121     Test4();
122     Test5();
123 
124     return 0;
125 }
View Code