题目:给定链表的头指针和一个结点指针,在O(1)时间删除该结点。
函数的声明如下: void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted);
分析:这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解。
注意函数的第一个参数pListHead是一个指向指针的指针。例如,当我们往一个空链表中插入一个结点时,新插入的结点就是链表的头指针。由于此时会改动头指针,因此必须把pHead参数设为指向指针的指针,否则出了这个函数pHead仍然是一个空指针。
在链表中删除一个结点,最常规的做法是从链表的头结点开始,顺序查找要删除的结点,找到之后再删除。由于需要顺序查找,时间复杂度自然就是O(n) 了。
我们之所以需要从头结点开始查找要删除的结点,是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这个时候我们实际删除的是它的下一个结点,由于我们已经得到实际删除的结点的前面一个结点,因此完全是可以实现的。当然,在删除之前,我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时,时间复杂度为O(1)。
上面的思路还有一个问题:如果删除的结点位于链表的尾部,没有下一个结点,怎么办?我们仍然从链表的头结点开始,顺便遍历得到给定结点的前序结点,并完成删除操作。
最后需要注意的是,如果链表中只有一个结点,而我们又要删除链表的头结点,此时我们在删除结点后,还需要把链表的头结点设置为NULL。
需要全面的考虑到删除的结点位于链表的尾部及输入的链表只有一个结点的特殊情况。
这个时候时间复杂度是O(n)。那题目要求我们需要在O(1)时间完成删除操作,我们的算法是不是不符合要求?实际上,假设链表总共有n个结点,我们的算法在n-1总情况下时间复杂度是 O(1),只有当给定的结点处于链表末尾的时候,时间复杂度为O(n)。那么平均时间复杂度[(n-1)*O(1)+O(n)]/n,仍然为O(1)。
1 void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
2 {
3 if(!pListHead || !pToBeDeleted)
4 return;
5
6 // 要删除的结点不是尾结点
7 if(pToBeDeleted->m_pNext != NULL)
8 {
9 ListNode* pNext = pToBeDeleted->m_pNext;
10 pToBeDeleted->m_nValue = pNext->m_nValue;
11 pToBeDeleted->m_pNext = pNext->m_pNext;
12
13 delete pNext;
14 pNext = NULL;
15 }
16 // 链表只有一个结点,删除头结点(也是尾结点)
17 else if(*pListHead == pToBeDeleted)
18 {
19 delete pToBeDeleted;
20 pToBeDeleted = NULL;
21 *pListHead = NULL;
22 }
23 // 链表中有多个结点,删除尾结点
24 else
25 {
26 ListNode* pNode = *pListHead;
27 while(pNode->m_pNext != pToBeDeleted)
28 {
29 pNode = pNode->m_pNext;
30 }
31
32 pNode->m_pNext = NULL;
33 delete pToBeDeleted;
34 pToBeDeleted = NULL;
35 }
36 }
37
38 参考代码
实现代码:
1 #include<iostream>
2 using namespace std;
3
4 typedef struct ListNode
5 {
6 int m_nKey;
7 struct ListNode *m_pNext;
8 }ListNode , *LinkList;
9
10 void InsertList(LinkList &L , int data) //头插入
11 {
12 ListNode *p = new ListNode();
13 p->m_nKey = data;
14 if(NULL == L)
15 p->m_pNext = NULL;
16 else
17 p->m_pNext = L;
18 L = p;
19 }
20
21 void PrintList(LinkList L) //打印链表
22 {
23 ListNode *p = L;
24 while(p)
25 {
26 cout<<p->m_nKey<<" ";
27 p = p->m_pNext;
28 }
29 cout<<endl;
30 }
31
32
33 void DeleteNode(LinkList &L , ListNode *pToBeDeleted) //删除链表L中的pToBeDeleted结点
34 {
35 if(!L || !pToBeDeleted)
36 return;
37 //要删除的结点不是尾结点
38 if(pToBeDeleted->m_pNext != NULL)
39 {
40 ListNode *pNext = pToBeDeleted->m_pNext;
41 pToBeDeleted->m_nKey = pNext->m_nKey;
42 pToBeDeleted->m_pNext = pNext->m_pNext;
43
44 delete pNext;
45 pNext = NULL;
46 }
47 //链表只有一个结点,删除头结点(也是尾结点)
48 else if(L == pToBeDeleted)
49 {
50 delete pToBeDeleted;
51 pToBeDeleted = NULL;
52 L = NULL;
53 }
54 //链表中有多个结点,删除尾结点
55 else
56 {
57 ListNode *pNode = L;
58 while(pNode->m_pNext != pToBeDeleted)
59 {
60 pNode = pNode->m_pNext;
61 }
62 pNode->m_pNext = NULL;
63 delete pToBeDeleted;
64 pToBeDeleted = NULL;
65
66 }
67 }
68
69 void main()
70 {
71 LinkList L = NULL;
72 ListNode *p;
73 int n;
74 InsertList(L, 3);
75 InsertList(L, 7);
76 InsertList(L, 12);
77 InsertList(L, 56);
78 InsertList(L, 33);
79 InsertList(L, 78);
80 InsertList(L, 20);
81 InsertList(L, 89);
82
83 PrintList(L);
84 cout<<"请输入要删除的节点:";
85 cin>>n;
86
87 p=L;
88 while(p->m_nKey!=n && p)
89 p=p->m_pNext;
90
91 if(!p)
92 {
93 cout<<"不存在这样的节点!"<<endl;
94 return;
95 }
96 else
97 DeleteNode(L, p);
98
99 cout<<"删除后的链表:";
100 PrintList(L);
101
102 }
完整代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 struct ListNode
5 {
6 int m_nValue;
7 ListNode* m_pNext;
8 };
9
10 void PrintList(ListNode* pHead)
11 {
12 printf("PrintList starts.\n");
13
14 ListNode* pNode = pHead;
15 while(pNode != NULL)
16 {
17 printf("%d\t", pNode->m_nValue);
18 pNode = pNode->m_pNext;
19 }
20
21 printf("\nPrintList ends.\n");
22 }
23
24 void PrintListNode(ListNode* pNode)
25 {
26 if(pNode == NULL)
27 {
28 printf("The node is NULL\n");
29 }
30 else
31 {
32 printf("The key in node is %d.\n", pNode->m_nValue);
33 }
34 }
35
36 ListNode* CreateListNode(int value)
37 {
38 ListNode* pNode = new ListNode();
39 pNode->m_nValue = value;
40 pNode->m_pNext = NULL;
41
42 return pNode;
43 }
44
45 void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
46 {
47 if(pCurrent == NULL)
48 {
49 printf("Error to connect two nodes.\n");
50 exit(1);
51 }
52
53 pCurrent->m_pNext = pNext;
54 }
55
56 void DestroyList(ListNode* pHead)
57 {
58 ListNode* pNode = pHead;
59 while(pNode != NULL)
60 {
61 pHead = pHead->m_pNext;
62 delete pNode;
63 pNode = pHead;
64 }
65 }
66
67 //----------------------------------------------------------------
68
69 void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
70 {
71 if(!pListHead || !pToBeDeleted)
72 return;
73
74 // 要删除的结点不是尾结点
75 if(pToBeDeleted->m_pNext != NULL)
76 {
77 ListNode* pNext = pToBeDeleted->m_pNext;
78 pToBeDeleted->m_nValue = pNext->m_nValue;
79 pToBeDeleted->m_pNext = pNext->m_pNext;
80
81 delete pNext;
82 pNext = NULL;
83 }
84 // 链表只有一个结点,删除头结点(也是尾结点)
85 else if(*pListHead == pToBeDeleted)
86 {
87 delete pToBeDeleted;
88 pToBeDeleted = NULL;
89 *pListHead = NULL;
90 }
91 // 链表中有多个结点,删除尾结点
92 else
93 {
94 ListNode* pNode = *pListHead;
95 while(pNode->m_pNext != pToBeDeleted)
96 {
97 pNode = pNode->m_pNext;
98 }
99
100 pNode->m_pNext = NULL;
101 delete pToBeDeleted;
102 pToBeDeleted = NULL;
103 }
104 }
105
106 // ====================测试代码====================
107 void Test(ListNode* pListHead, ListNode* pNode)
108 {
109 printf("The original list is: \n");
110 PrintList(pListHead);
111
112 printf("The node to be deleted is: \n");
113 PrintListNode(pNode);
114
115 DeleteNode(&pListHead, pNode);
116
117 printf("The result list is: \n");
118 PrintList(pListHead);
119 }
120
121 // 链表中有多个结点,删除中间的结点
122 void Test1()
123 {
124 ListNode* pNode1 = CreateListNode(1);
125 ListNode* pNode2 = CreateListNode(2);
126 ListNode* pNode3 = CreateListNode(3);
127 ListNode* pNode4 = CreateListNode(4);
128 ListNode* pNode5 = CreateListNode(5);
129
130 ConnectListNodes(pNode1, pNode2);
131 ConnectListNodes(pNode2, pNode3);
132 ConnectListNodes(pNode3, pNode4);
133 ConnectListNodes(pNode4, pNode5);
134
135 Test(pNode1, pNode3);
136
137 DestroyList(pNode1);
138 }
139
140 // 链表中有多个结点,删除尾结点
141 void Test2()
142 {
143 ListNode* pNode1 = CreateListNode(1);
144 ListNode* pNode2 = CreateListNode(2);
145 ListNode* pNode3 = CreateListNode(3);
146 ListNode* pNode4 = CreateListNode(4);
147 ListNode* pNode5 = CreateListNode(5);
148
149 ConnectListNodes(pNode1, pNode2);
150 ConnectListNodes(pNode2, pNode3);
151 ConnectListNodes(pNode3, pNode4);
152 ConnectListNodes(pNode4, pNode5);
153
154 Test(pNode1, pNode5);
155
156 DestroyList(pNode1);
157 }
158
159 // 链表中有多个结点,删除头结点
160 void Test3()
161 {
162 ListNode* pNode1 = CreateListNode(1);
163 ListNode* pNode2 = CreateListNode(2);
164 ListNode* pNode3 = CreateListNode(3);
165 ListNode* pNode4 = CreateListNode(4);
166 ListNode* pNode5 = CreateListNode(5);
167
168 ConnectListNodes(pNode1, pNode2);
169 ConnectListNodes(pNode2, pNode3);
170 ConnectListNodes(pNode3, pNode4);
171 ConnectListNodes(pNode4, pNode5);
172
173 Test(pNode1, pNode1);
174
175 DestroyList(pNode1);
176 }
177
178 // 链表中只有一个结点,删除头结点
179 void Test4()
180 {
181 ListNode* pNode1 = CreateListNode(1);
182
183 Test(pNode1, pNode1);
184 }
185
186 // 链表为空
187 void Test5()
188 {
189 Test(NULL, NULL);
190 }
191
192 int main()
193 {
194 Test1();
195 Test2();
196 Test3();
197 Test4();
198 Test5();
199
200 return 0;
201 }