5/21 每日一題 (鍊結串列)

 203. Remove Linked List Elements

Easy

7.2K

209

Companies

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

 

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:

        #定義一個新節點

        newlink=ListNode()

        cur = newlink #保留一個最後回傳用

       

        current = head

        while current: #走訪head每一個節點

            if current.val != val: #當不是val的時候,放入新鍊表

                cur.next = current

                cur = cur.next  #新鍊表指針移動

            current = current.next #持續走訪

        cur.next = None

    #斷開新鍊表的尾巴節點連接

    #否則會繼續按照原始鍊結的模式將next為None的節點放入新鍊表中

        return newlink.next

            #因為一開始定義的newlink是空節點,所以回傳newlink.next

參考解答

Before writing any code, it's good to make a list of edge cases that we need to consider. This is so that we can be certain that we're not overlooking anything while coming up with our algorithm, and that we're testing all special cases when we're ready to test. These are the edge cases that I came up with.

1. The linked list is empty, i.e. the head node is None.
2. Multiple nodes with the target value in a row.
3. The head node has the target value.
4. The head node, and any number of nodes immediately after it have the target value.
5. All of the nodes have the target value.
6. The last node has the target value.

So with that, this is the algorithm I came up with.

在編寫任何代碼之前，最好列出我們需要考慮的邊緣情況。這樣我們就可以確定在提出算法時我們不會忽略任何東西，並且當我們準備好測試時我們正在測試所有特殊情況。這些是我想出的邊緣案例。

1. 鍊錶為空，即頭節點為None。
2. 連續具有目標值的多個節點。
3. 頭節點具有目標值。
4. 頭節點和緊隨其後的任意數量的節點都具有目標值。
5. 所有節點都具有目標值。
6. 最後一個節點具有目標值。

因此，這就是我想出的算法。

class Solution:
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        
        dummy_head = ListNode(-1)
        dummy_head.next = head
        
        current_node = dummy_head
        while current_node.next != None:
            if current_node.next.val == val:
                current_node.next = current_node.next.next
            else:
                current_node = current_node.next
                
        return dummy_head.next

為了避免將“頭部”視為特殊的需要，該算法使用“虛擬”頭部。這大大簡化了代碼，特別是在需要刪除頭部和緊隨其後的一些節點的情況下。

然後，我們跟踪我們到達的當前節點，並展望它的下一個節點，只要它存在。如果current_node.next確實需要刪除，那麼我們只需將其替換為current_node.next.next. 我們知道這總是“安全的”，因為current_node.next它絕對不是 None（循環條件確保了這一點），所以我們可以安全地訪問它的next.

否則，我們知道current_node.next應該保留它，因此我們繼續current_node成為current_node.next.

循環條件只需要檢查current_node.next != None. 它不需要檢查的原因current_node != None是因為這是不可能達到的狀態。這樣想：我們曾經做過的唯一情況current_node = current_node.next是在循環已經確認current_node.next不是 None 之後立即執行。

該算法需要O(1)額外的空間並花費O(n)時間。

In order to save the need to treat the "head" as special, the algorithm uses a "dummy" head. This simplifies the code greatly, particularly in the case of needing to remove the head AND some of the nodes immediately after it.

Then, we keep track of the current node we're up to, and look ahead to its next node, as long as it exists. If current_node.next does need removing, then we simply replace it with current_node.next.next. We know this is always "safe", because current_node.next is definitely not None (the loop condition ensures that), so we can safely access its next.

Otherwise, we know that current_node.next should be kept, and so we move current_node on to be current_node.next.

The loop condition only needs to check that current_node.next != None. The reason it does not need to check that current_node != None is because this is an impossible state to reach. Think about it this way: The ONLY case that we ever do current_node = current_node.next in is immediately after the loop has already confirmed that current_node.next is not None.

The algorithm requires O(1) extra space and takes O(n) time.