要求
- 给定单向链表的头指针和一个节点指针，在O（1）时间内删除该节点
- 常规思路：从头节点a开始顺序遍历，发现p指向要删除的节点i，然后把p的m_pNext指向i的下一个节点j，时间复杂度O（n）
- O（1）的思路：把i的下一个节点j的内容复制到i，然后令i指向j的下一个节点
- 考虑特殊情况：
- 链表只有一个节点：删除该节点
- 删除尾节点：遍历至倒数第二个节点，删除
DeleteNodeList.cpp
1 #include <cstdio>
2 #include "List.h"
3
4 void DeleteNode(ListNode** pListHead,ListNode* pToBeDeleted){
5 if(!pListHead || !pToBeDeleted)
6 return;
7 if(pToBeDeleted->m_pNext != nullptr){
8 ListNode* pNext = pToBeDeleted->m_pNext;
9 pToBeDeleted->m_nValue = pNext->m_nValue;
10 pToBeDeleted->m_pNext = pNext->m_pNext;
11 delete pNext;
12 pNext=nullptr;
13 }
14 else if(*pListHead == pToBeDeleted){
15 delete pToBeDeleted;
16 pToBeDeleted = nullptr;
17 *pListHead = nullptr;
18 }else{
19 ListNode* pNode = *pListHead;
20 while(pNode->m_pNext != pToBeDeleted){
21 pNode = pNode->m_pNext;
22 }
23 pNode->m_pNext = nullptr;
24 delete pToBeDeleted;
25 pToBeDeleted = nullptr;
26 }
27 }
28
29 void Test(ListNode* pListHead,ListNode* pNode){
30 printf("The original list is:\n");
31 PrintList(pListHead);
32
33 printf("The node to be deleted is:\n");
34 PrintListNode(pNode);
35
36 DeleteNode(&pListHead,pNode);
37
38 printf("The result list is:\n");
39 PrintList(pListHead);
40 }
41
42 void Test1(){
43 ListNode* pNode1 = CreateListNode(1);
44 ListNode* pNode2 = CreateListNode(2);
45 ListNode* pNode3 = CreateListNode(3);
46 ListNode* pNode4 = CreateListNode(4);
47 ListNode* pNode5 = CreateListNode(5);
48
49 ConnectListNodes(pNode1,pNode2);
50 ConnectListNodes(pNode2,pNode3);
51 ConnectListNodes(pNode3,pNode4);
52 ConnectListNodes(pNode4,pNode5);
53
54 Test(pNode1,pNode3);
55
56 DestroyList(pNode1);
57 }
58
59 void Test2()
60 {
61 ListNode* pNode1 = CreateListNode(1);
62 ListNode* pNode2 = CreateListNode(2);
63 ListNode* pNode3 = CreateListNode(3);
64 ListNode* pNode4 = CreateListNode(4);
65 ListNode* pNode5 = CreateListNode(5);
66
67 ConnectListNodes(pNode1, pNode2);
68 ConnectListNodes(pNode2, pNode3);
69 ConnectListNodes(pNode3, pNode4);
70 ConnectListNodes(pNode4, pNode5);
71
72 Test(pNode1, pNode5);
73
74 DestroyList(pNode1);
75 }
76
77 // 链表中有多个结点，删除头结点
78 void Test3()
79 {
80 ListNode* pNode1 = CreateListNode(1);
81 ListNode* pNode2 = CreateListNode(2);
82 ListNode* pNode3 = CreateListNode(3);
83 ListNode* pNode4 = CreateListNode(4);
84 ListNode* pNode5 = CreateListNode(5);
85
86 ConnectListNodes(pNode1, pNode2);
87 ConnectListNodes(pNode2, pNode3);
88 ConnectListNodes(pNode3, pNode4);
89 ConnectListNodes(pNode4, pNode5);
90
91 Test(pNode1, pNode1);
92
93 DestroyList(pNode1);
94 }
95
96 // 链表中只有一个结点，删除头结点
97 void Test4()
98 {
99 ListNode* pNode1 = CreateListNode(1);
100
101 Test(pNode1, pNode1);
102 }
103
104 // 链表为空
105 void Test5()
106 {
107 Test(nullptr, nullptr);
108 }
109 int main(int argc,char* argv[]){
110 Test1();
111 Test2();
112 Test3();
113 Test4();
114 Test5();
115 return 0;
116 }
List.h
1 struct ListNode{
2 int m_nValue;
3 ListNode* m_pNext;
4 };
5
6 ListNode* CreateListNode(int value);
7 void ConnectListNodes(ListNode* pCurrent,ListNode* pNext);
8 void PrintListNode(ListNode* pNode);
9 void PrintList(ListNode* pHead);
10 void DestroyList(ListNode* pHead);
11 void AddToTail(ListNode** pHead,int value);
12 void RemoveNode(ListNode** pHead,int value);
List.cpp
1 #include "List.h"
2 #include <stdio.h>
3 #include <stdlib.h>
4
5 ListNode* CreateListNode(int value){
6 ListNode* pNode = new ListNode();
7 pNode->m_nValue = value;
8 pNode->m_pNext = nullptr;
9 return pNode;
10 }
11
12 void ConnectListNodes(ListNode* pCurrent,ListNode* pNext){
13 if(pCurrent == nullptr){
14 printf("Error to connect two nodes.\n");
15 exit(1);
16 }
17 pCurrent->m_pNext = pNext;
18 }
19
20 void PrintListNode(ListNode* pNode){
21 if(pNode == nullptr){
22 printf("The node is nullptr\n");
23 }
24 else{
25 printf("The key in node is %d.\n",pNode->m_nValue);
26 }
27 }
28
29 void PrintList(ListNode* pHead){
30 printf("PrintList starts.\n");
31 ListNode* pNode = pHead;
32 while(pNode != nullptr){
33 printf("%d\t",pNode->m_nValue);
34 pNode = pNode->m_pNext;
35 }
36 printf("\nPrintList ends.\n");
37 }
38
39 void DestroyList(ListNode* pHead){
40 ListNode* pNode = pHead;
41 while(pNode != nullptr){
42 pHead = pHead->m_pNext;
43 delete pNode;
44 pNode = pHead;
45 }
46 }
47
48 void AddToTail(ListNode** pHead,int value){
49 ListNode* pNew = new ListNode();
50 pNew->m_nValue = value;
51 pNew->m_pNext = nullptr;
52 if(*pHead == nullptr){
53 *pHead = pNew;
54 }else{
55 ListNode* pNode = *pHead;
56 while(pNode->m_pNext != nullptr)
57 pNode = pNode->m_pNext;
58 pNode->m_pNext = pNew;
59 }
60 }
61
62 void RemoveNode(ListNode** pHead,int value){
63 if(pHead == nullptr || *pHead == nullptr)
64 return;
65 ListNode* pToBeDeleted = nullptr;
66 if((*pHead)->m_nValue == value){
67 pToBeDeleted = *pHead;
68 *pHead = (*pHead)->m_pNext;
69 }else{
70 ListNode* pNode = *pHead;
71 while(pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue != value)
72 pNode = pNode->m_pNext;
73 if(pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue == value){
74 pToBeDeleted = pNode->m_pNext;
75 pNode->m_pNext = pNode->m_pNext->m_pNext;
76 }
77 }
78 if(pToBeDeleted != nullptr){
79 delete pToBeDeleted;
80 pToBeDeleted = nullptr;
81 }
82 }
总结
- 操作数据用指针（如修改数据的内容），操作指针用指针的指针（如修改指针的指向）
- 想要改变一个值，就要先得到它的地址，想要改变一个指针，就要先得到指针的地址（指针的指针）
- 在.h中定义数据结构体，声明函数；在.cpp中实现函数
- new和delete配套使用，new申请内存，delete释放new分配的对象指针指向的内存，之后还要清空指针才能完成彻底删除