2020年4月7日 星期二

Leetcode題解 Python：Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.
給一串 Linked List ，要刪除其中節點等於 val 的節點，並回傳頭節點。

這題不難，如果用快慢指針，就需要針對刪除頭部的狀況做判斷。

對我來說，要針對非題目所求的特別情況去做 if 判斷，這種寫法在我心中的「泛用性」就在及格邊緣搖搖欲墜。

這題已經離開了雙指針的子章節，應該是可以不用雙指針去解。

用了遞迴寫法，雖然版面簡潔許多，不過時間複雜度是紮實的 O(N)，每個節點都會修改。
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        def nextNode(node):
            if node:
                node.next = nextNode(node.next)            
                if node.val == val: return node.next                    
            return node
        return nextNode(head)

上一題說到將 Linked List 反序，如果用反序的概念，也就是把目標值丟到最前方去。如此，最後只需要從頭跑 Linked List 直到不為目標值的時候，再把該節回傳。
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:       
        if not head: return head
        FP =  SP = head
        FP = FP.next
        while FP:
            if FP.val == val:
                SP.next = SP.next.next
                FP.next = head
                head = FP
                FP = SP.next
            else:
                SP = SP.next
                FP = FP.next
        #
        while head and head.val == val:
            head = head.next
        return head
如果頭部移除的情形會很困擾，看了前段班的寫法，可以加入了暫時根節變成新頭根節，這樣可以把一切都當成子根節處理，最後回傳暫時根節的下一個(原頭根節)即可，就不需要針對頭根節移除自身做額外寫法。
# 前段班大神寫法 
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:       
        head_holder = ListNode(0) # the value does not matter
        head_holder.next = head
        
        cur = head_holder
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next

        return head_holder.next
於
標籤： ,