李代桃僵 刪除節點 Delete Node in a Linked List_Leetcode #237
題目敘述
題目給定一個鏈結串列中的節點Node，要求我們從鏈結串列中刪除該節點。
題目保證該節點不是tail node。
題目要求我們in-place原位操作。
測試範例
Example 1:
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
Example 2:
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.
約束條件
Constraints:
- The number of the nodes in the given list is in the range
[2, 1000].
節點總數目介於2~1000之間。
-1000 <= Node.val <= 1000
節點值介於-1000~1000之間。
- The value of each node in the list is unique.
每個節點值都不同。
- The
nodeto be deleted is in the list and is not a tail node.
目標節點絕對存在，而且不是tail node。
演算法 李代桃僵
其實這題算是有變化，需要轉個彎思考的題目。
一般來說，Linked list的題目會先給head node，再給目標節點或目標值進行操作。
但是這題只有給目標節點，要求我們刪除目標節點。
困難點就在於，要如何更新linkage 新的連接?
原本輸入的樣子是
... -> 前一個節點 -> 目標節點 -> 後一個節點 -> ...
刪除之後，應該要變成
... -> 前一個節點 -> 後一個節點 -> ...
但是題目沒有給head node，根本沒辦法知道 前一個節點是誰。
因此，就有了替代的解法，李代桃僵(俗稱的替死鬼)，原本是要刪除目標節點，但是我們改成刪除後一個節點，並且拷貝後一個節點的值到我自己身上，這樣的形狀就會和原本的相同。
原本輸入的樣子是
... -> 前一個節點 -> 目標節點 -> 後一個節點 -> ...
李代桃僵，刪除後一個節點，變成
... -> 前一個節點 -> 目標節點(擁有原本後一個節點的節點值) -> ...
示意圖
程式碼 李代桃僵
class Solution:
def deleteNode(self, node):
# locate victim node
victim_node = node.next
# overwrite node's value by victim node's value
node.val = victim_node.val
# break the linkage of victim node
node.next = victim_node.next
# release victim node
del victim_node
return
複雜度分析
時間複雜度: O(1)
只涉及兩個節點的操作，為常數時間。
空間複雜度: O(1)
所需要的都是臨時變數，為常數級別O(1)。
關鍵知識點
困難點就在於，要如何更新linkage 新的連接?
題目沒有給head node，根本沒辦法知道 前一個節點是誰。
因此，就有了替代的解法，李代桃僵(俗稱的替死鬼)，原本是要刪除目標節點，但是我們改成刪除後一個節點，並且拷貝後一個節點的值到我自己身上，這樣的形狀就會和原本的相同。
Reference
