題目：以O(1)的時間復雜度刪除單鏈表中的某個節(jié)點

自己所寫代碼如下：

//以O(1)時間刪除鏈表節(jié)點 //要求：單向鏈表，頭指針，待刪節(jié)點指針//鏈表節(jié)點 struct ListNode {int m_nValue;ListNode* m_pNext; }; //O(n)的解法：從頭遍歷，找到pToBeDeleted所指節(jié)點的前一個節(jié)點再進行刪除 void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted) {if(pListHead == NULL || *pListHead == NULL || pToBeDeleted == NULL)return;ListNode* pNode = *pListHead;if(pNode == pToBeDeleted) //對pToBeDeleted指向頭結(jié)點情況的處理{*pListHead = (*pListHead)->m_pNext;delete pToBeDeleted;pToBeDeleted = NULL;}else{while(pNode->m_pNext != NULL && pNode->m_pNext != pToBeDeleted)pNode = pNode->m_pNext ;if(pNode->m_pNext == NULL){cout<<"pToBeDeleted不在鏈表中！"<<endl;return;}pNode->m_pNext = pToBeDeleted->m_pNext;delete pToBeDeleted;pToBeDeleted = NULL;}}//O(1)的解法：復制后一個節(jié)點以覆蓋待刪節(jié)點，再刪除重復的后一個節(jié)點 void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted) {if(pListHead == NULL || *pListHead == NULL || pToBeDeleted == NULL)return;ListNode* pNode = *pListHead;if(pNode == pToBeDeleted){*pListHead = (*pListHead)->m_pNext;delete pToBeDeleted;pToBeDeleted = NULL;}else{pNode = pToBeDeleted->m_pNext;//排除pToBeDeleted指向尾節(jié)點的情形if(pNode == NULL){pNode = *pListHead;while(pNode->m_pNext != pToBeDeleted)pNode = pNode->m_pNext ;pNode->m_pNext = NULL;delete pToBeDeleted;pToBeDeleted = NULL;}else{pToBeDeleted->m_nValue = pNode->m_nValue;pToBeDeleted->m_pNext = pNode->m_pNext;delete pNode;pNode = NULL;}} }

在以上O(1)的代碼中，自己的想法有些呆板，具體來說：采用復制覆蓋的方法則應考慮的是pToBeDeleted指向尾節(jié)點的特殊情況（此時，無法復制！）

而非pToBeDeleted指向頭結(jié)點的情況（這是O(n)的特殊情況！）！！！

O(n)的方法：需要找前驅(qū)節(jié)點，所以考慮頭結(jié)點的特殊情況；

O(1)的方法：需要找后繼節(jié)點，所以考慮尾節(jié)點的特殊情況。

代碼修改如下：

//O(1)的解法：復制后一個節(jié)點以覆蓋待刪節(jié)點，再刪除重復的后一個節(jié)點 void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted) {if(pListHead == NULL || *pListHead == NULL || pToBeDeleted == NULL)return;ListNode* pNode = pToBeDeleted->m_pNext;//排除pToBeDeleted指向尾節(jié)點的情形if(pNode == NULL){pNode = *pListHead;if(pNode == pToBeDeleted){delete pToBeDeleted;*pListHead = pToBeDeleted = NULL;}else{while(pNode->m_pNext != pToBeDeleted)pNode = pNode->m_pNext;pNode->m_pNext = NULL;delete pToBeDeleted;pToBeDeleted = NULL;}}else{pToBeDeleted->m_nValue = pNode->m_nValue;pToBeDeleted->m_pNext = pNode->m_pNext;delete pNode;pNode = NULL;}}

和參考代碼相一致！贊一個！

?

總結(jié)：1、突破常規(guī)思維，刪除節(jié)點不一定需要從頭遍歷鏈表，可以用下一結(jié)點復制并覆蓋待刪節(jié)點，最后再刪除重復的下一結(jié)點。

　　　2、考慮問題全面性：若待刪節(jié)點為尾節(jié)點，則下一個節(jié)點為空；若整個鏈表僅一個節(jié)點，刪除后，頭結(jié)點同時設為NULL。

　　　　 ?這些都需要特殊對待！！！

?

轉(zhuǎn)載于:https://www.cnblogs.com/hello-yz/p/3251464.html

總結(jié)

以上是生活随笔為你收集整理的剑指offer--面试题13的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。