面試題13：在O（1）時(shí)間刪除鏈表結(jié)點(diǎn)
題目：給定單向鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，定義一個(gè)函數(shù)在 O（1）時(shí)間刪除該結(jié)點(diǎn)。鏈表結(jié)點(diǎn)與函數(shù)的定義如下：

struct ListNode {int value;ListNode *next; };void DeleteNode(ListNode ** pListHead, ListNode *pToBeDeleted);

代碼如下:

struct ListNode {int value;ListNode *next; };void DeleteNode(ListNode ** pListHead, ListNode *pToBeDeleted) {if (!pListHead || !pToBeDeleted) return;//要?jiǎng)h除的結(jié)點(diǎn)不是尾結(jié)點(diǎn)if (pToBeDeleted->next != nullptr){ListNode *pNext = pToBeDeleted->next;pToBeDeleted->value = pNext->value;pToBeDeleted->next = pNext->next;delete pNext;pNext = nullptr;}//鏈表只有一個(gè)結(jié)點(diǎn)，刪除頭結(jié)點(diǎn)(也是尾結(jié)點(diǎn))else if (*pListHead == pToBeDeleted){delete pToBeDeleted;pToBeDeleted = nullptr;*pListHead = nullptr;}//鏈表中有多個(gè)結(jié)點(diǎn)，刪除尾結(jié)點(diǎn)else{ListNode *pNode = *pListHead;while (pNode->next != pToBeDeleted){pNode = pNode->next;}pNode->next = nullptr;delete pToBeDeleted;pToBeDeleted = nullptr;} }

測(cè)試用例：
● 功能測(cè)試（從有多個(gè)結(jié)點(diǎn)的鏈表的中間刪除一個(gè)結(jié)點(diǎn)，從有多個(gè)結(jié)點(diǎn)的鏈表中刪除頭結(jié)點(diǎn)，從有多個(gè)結(jié)點(diǎn)的鏈表中刪除尾結(jié)點(diǎn)，從只有一個(gè)結(jié)點(diǎn)的鏈表中刪除唯一的結(jié)點(diǎn)）。
● 特殊輸入測(cè)試（指向鏈表頭結(jié)點(diǎn)指針的為 NULL 指針，指向要?jiǎng)h除的結(jié)點(diǎn)為NULL指針）。
本題考點(diǎn)：
● 考查應(yīng)聘者對(duì)鏈表的編程能力。
● 考查應(yīng)聘者的創(chuàng)新思維能力。這道題要求應(yīng)聘者打破常規(guī)的思維模式。當(dāng)我們想刪除一個(gè)結(jié)點(diǎn)時(shí)，并不一定要?jiǎng)h除這個(gè)結(jié)點(diǎn)本身。可以先把下一個(gè)結(jié)點(diǎn)的內(nèi)容復(fù)制出來(lái)覆蓋被刪除結(jié)點(diǎn)的內(nèi)容，然后把下一個(gè)結(jié)點(diǎn)刪除。這種思路不是很容易想到的。
● 考查應(yīng)聘者思維的全面性。即使應(yīng)聘者想到刪除下一個(gè)結(jié)點(diǎn)這個(gè)辦法，也未必能通過(guò)這輪面試。應(yīng)聘者要全面考慮到刪除的結(jié)點(diǎn)位于鏈表的尾部及輸入的鏈表只有一個(gè)結(jié)點(diǎn)這些特殊情況。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[剑指offer]面试题13：在O（1）时间删除链表结点的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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