如題：

這道題要求在O(1)時間內刪除鏈表節點。

常規解法是遍歷鏈表，找到所需元素，使其前繼節點的next指針指向待刪節點的next指針，時間復雜度位O(n)，不滿足要求。除了遍歷之外，還有一種更好的辦法刪除結點，如果結點存在后繼元素的話，可以直接將后繼元素所有值復制到待刪元素，這時候直接刪除后繼即可，如果位于尾節點，則遍歷鏈表，對于鏈表中只有一個元素的情況，這時候，待刪結點即是頭節點又是尾節點則需要特殊處理。這種方式的平均時間復雜度為O((n-1)O(1) + O(n))/n) = O(1)，滿足要求。

?下面是本題c++編碼:

void DeleteNode(ListNode **pListHead, ListNode *pToBeDeleted) {if (!pListHead || !pToBeDeleted)return;//要刪除的節點不是尾節點if (pToBeDeleted->m_pNext != nullptr){ListNode *pNext = pToBeDeleted->m_pNext;pToBeDeleted->m_nValue = pNext->m_nValue;pToBeDeleted->m_pNext = pNext->m_pNext;delete pNext;pNext = nullptr;}//鏈表只有一個節點，刪除頭節點(也是尾節點)else if (*pListHead == pToBeDeleted){delete pToBeDeleted;pToBeDeleted = nullptr;*pListHead = nullptr;}//鏈表中有多個節點，刪除尾節點else{ListNode *pNext = *pListHead;while (pNext->m_pNext != pToBeDeleted){pNext = pNext->m_pNext;}pNext->m_pNext = nullptr;delete pToBeDeleted;pToBeDeleted = nullptr;} }

=============================================================================================

Linux應用程序、內核、驅動、后臺開發交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結

以上是生活随笔為你收集整理的《剑指offer》c++版本 18.删除链表的结点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。