解題說明
Delete Node in a Linked List
題目描述:給定一個鏈結串列中的某個節點(保證不是尾節點),在不給定串列頭節點的情況下,將該節點從串列中刪除。
解題思路:這題的關鍵洞察是:我們無法「真正」刪除給定的節點(因為沒有其前驅節點的參照),但可以將其「偽裝」成下一個節點後再刪除下一個節點。具體做法:將下一個節點的值複製到當前節點,然後讓當前節點的 next 跳過下一個節點指向下下個節點,即可達到「刪除」的效果。題目保證給定節點不是尾節點,因此 node->next 必然存在。這是一個考驗對鏈結串列本質理解的巧妙題目。
C++ 解法
複雜度分析
時間複雜度:O(1) — 只進行常數次指標操作和值複製。
空間複雜度:O(1) — 不需要任何額外空間。
虛擬碼
1. Copy the value of node.next into node 2. Set node.next = node.next.next 3. (The original next node is now effectively removed)
其他解法
標準刪除法(需要頭節點):從頭遍歷找到前驅節點,將 prev->next = node->next。此方法是真正的刪除,但本題不提供頭節點。
節點替換討論:本題解法本質上是「值複製 + 跳過下一節點」,被刪除的是記憶體中的 node->next,而非 node 本身。在有些語言中需注意記憶體釋放問題。
延伸思考
- 如果給定節點是尾節點,此解法會失效,實際上有辦法在不知道頭節點的情況下刪除尾節點嗎?
- 這個解法對節點的記憶體管理有何影響?在 C++ 中是否需要釋放被「跳過」的節點記憶體?
- 如何設計一個雙向鏈結串列,使得刪除任意節點都能在 O(1) 完成,且不需要此技巧?