題目：給定鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，在O(1)時(shí)間刪除該結(jié)點(diǎn)。鏈表結(jié)點(diǎn)的定義如下：

struct ListNode {int m_nKey;ListNode* m_pNext; };

函數(shù)的聲明如下：

void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

分析：這是一道廣為流傳的Google面試題，能有效考察我們的編程基本功，還能考察我們的反應(yīng)速度，更重要的是，還能考察我們對(duì)時(shí)間復(fù)雜度的理解。

在鏈表中刪除一個(gè)結(jié)點(diǎn)，最常規(guī)的做法是從鏈表的頭結(jié)點(diǎn)開(kāi)始，順序查找要?jiǎng)h除的結(jié)點(diǎn)，找到之后再刪除。由于需要順序查找，時(shí)間復(fù)雜度自然就是O(n)?了。

我們之所以需要從頭結(jié)點(diǎn)開(kāi)始查找要?jiǎng)h除的結(jié)點(diǎn)，是因?yàn)槲覀冃枰玫揭獎(jiǎng)h除的結(jié)點(diǎn)的前面一個(gè)結(jié)點(diǎn)。我們?cè)囍鴵Q一種思路。我們可以從給定的結(jié)點(diǎn)得到它的下一個(gè)結(jié)點(diǎn)。這個(gè)時(shí)候我們實(shí)際刪除的是它的下一個(gè)結(jié)點(diǎn)，由于我們已經(jīng)得到實(shí)際刪除的結(jié)點(diǎn)的前面一個(gè)結(jié)點(diǎn)，因此完全是可以實(shí)現(xiàn)的。當(dāng)然，在刪除之前，我們需要需要把給定的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)拷貝到給定的結(jié)點(diǎn)中。此時(shí)，時(shí)間復(fù)雜度為O(1)。

上面的思路還有一個(gè)問(wèn)題：如果刪除的結(jié)點(diǎn)位于鏈表的尾部，沒(méi)有下一個(gè)結(jié)點(diǎn)，怎么辦？我們?nèi)匀粡逆湵淼念^結(jié)點(diǎn)開(kāi)始，順便遍歷得到給定結(jié)點(diǎn)的前序結(jié)點(diǎn)，并完成刪除操作。這個(gè)時(shí)候時(shí)間復(fù)雜度是O(n)。

那題目要求我們需要在O(1)時(shí)間完成刪除操作，我們的算法是不是不符合要求？實(shí)際上，假設(shè)鏈表總共有n個(gè)結(jié)點(diǎn)，我們的算法在n-1總情況下時(shí)間復(fù)雜度是O(1)，只有當(dāng)給定的結(jié)點(diǎn)處于鏈表末尾的時(shí)候，時(shí)間復(fù)雜度為O(n)。那么平均時(shí)間復(fù)雜度[(n-1)*O(1)+O(n)]/n，仍然為O(1)。

基于前面的分析，我們不難寫(xiě)出下面的代碼。

參考代碼：

/// // Delete a node in a list // Input: pListHead - the head of list // pToBeDeleted - the node to be deleted /// void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted) {if(!pListHead || !pToBeDeleted)return;// if pToBeDeleted is not the last node in the listif(pToBeDeleted->m_pNext != NULL){// copy data from the node next to pToBeDeletedListNode* pNext = pToBeDeleted->m_pNext;pToBeDeleted->m_nKey = pNext->m_nKey;pToBeDeleted->m_pNext = pNext->m_pNext;// delete the node next to the pToBeDeleteddelete pNext;pNext = NULL;}// if pToBeDeleted is the last node in the listelse{// get the node prior to pToBeDeletedListNode* pNode = pListHead;while(pNode->m_pNext != pToBeDeleted){pNode = pNode->m_pNext; }// deleted pToBeDeletedpNode->m_pNext = NULL;delete pToBeDeleted;pToBeDeleted = NULL;} }

值得注意的是，為了讓代碼看起來(lái)簡(jiǎn)潔一些，上面的代碼基于兩個(gè)假設(shè)：（1）給定的結(jié)點(diǎn)的確在鏈表中；（2）給定的要?jiǎng)h除的結(jié)點(diǎn)不是鏈表的頭結(jié)點(diǎn)。不考慮第一個(gè)假設(shè)對(duì)代碼的魯棒性是有影響的。至于第二個(gè)假設(shè)，當(dāng)整個(gè)列表只有一個(gè)結(jié)點(diǎn)時(shí)，代碼會(huì)有問(wèn)題。但這個(gè)假設(shè)不算很過(guò)分，因?yàn)樵谟行╂湵淼膶?shí)現(xiàn)中，會(huì)創(chuàng)建一個(gè)虛擬的鏈表頭，并不是一個(gè)實(shí)際的鏈表結(jié)點(diǎn)。這樣要?jiǎng)h除的結(jié)點(diǎn)就不可能是鏈表的頭結(jié)點(diǎn)了。當(dāng)然，在面試中，我們可以把這些假設(shè)和面試官交流。這樣，面試官還是會(huì)覺(jué)得我們考慮問(wèn)題很周到的。

本文已經(jīng)收錄到《劍指Offer——名企面試官精講典型編程題》一書(shū)中，有改動(dòng)，書(shū)中的分析講解更加詳細(xì)。歡迎關(guān)注。

博主何海濤對(duì)本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請(qǐng)注明出處http://zhedahht.blog.163.com/。整理出版物請(qǐng)和作者聯(lián)系。

總結(jié)

以上是生活随笔為你收集整理的程序员面试题精选100题(33)-在O(1)时间删除链表结点[数据结构]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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