李代桃僵 刪除節點 Delete Node in a Linked List_Leetcode #237

davisuko null on Unsplash

題目敘述

題目給定一個鏈結串列中的節點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 node to 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

[1] Delete Node in a Linked List - LeetCode