2020年4月6日 星期一

Leetcode題解 Python： Linked List Cycle I & II

來到了 Linked List 章節，很快就遇到這個問題，問你ListNode是否有裡面有循環。

此題位於子章節 Two Pointer Technique，所以我不用直覺想到的 memo 紀錄步驟的遞迴解法。

示範提到，使用兩個 Pointer，一個快一個慢，快的一次走兩步，慢的走一步。

兩個 Pointer 的起點都是 head，如果有循環，Fast Pointer 遲早會追上 Slow Pointer
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: return head
        fastPointer, slowPointer = head, head
        while 1:
            # FastPointer go 2 steps forward
            for _ in range(2):
                if fastPointer.next:
                    fastPointer = fastPointer.next
                    if fastPointer == slowPointer: 
                        return True                            
                else:
                    return False
            # SlowPointer go 1 steps forward
            for _ in range(1):
                slowPointer = slowPointer.next


這種寫法可以減少記憶體使用，空間複雜度為 O(1)。

另外一種用 memo 紀錄步驟的方法。

紀錄步驟是需要用到不會重複的值，如果只是 val，除非保證不會有相同 val，不然可能會出錯。

最保險起見的方法，是使用記憶體位置，作為是否曾經走過的依據。

幸好物件可以直接加入set，而物件在set中做為比較的數值是記憶體位置。
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: return head
        memo = set()
        while head.next:
            if head in memo: return True
            memo.add(head)
            head = head.next
        return False
我在想，如果要得加入一個有用的變數在裡面，到底要怎麼加？這才是勾起我的興致的發想。 想出來了，硬是要在裡面加入的 steps 紀錄步數。 
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: return head
        fastPointer, slowPointer = head, head
        steps = 0
        while fastPointer.next:
            fastPointer, steps = fastPointer.next, steps+1
            if fastPointer == slowPointer: return True                                           
            if steps%2==1: slowPointer = slowPointer.next                
        return False
接著看到 II，這次要回傳循環起點，如果用 memo 紀錄，這個問題只是將回傳False改成當前的節點。 
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head: return head
        memo = set()
        while head.next:
            if head in memo: return head
            else: memo.add(head)
            head = head.next            
        return None
如果用快慢指針來解要怎麼辦？在兩者相遇之後，把慢指針移回原點，快慢指針每次都指往前一步，就會在循環起點相遇。

解釋：快2步，慢1步，當慢指針到了循環起點時，快指針在循環中也走了循環起點距離。而兩者的所剩距離是 循環長度 - 循環起點距離。
因此，慢指針往前「循環長度 - 循環起點距離」，兩者就會在循環內的 (循環長度 - 循環起點距離)位置上相遇。
此時把慢指針挪回起點，慢快指針同時走一步，前進 循環起點距離 步時，慢指針會來到 循環起點， 快指針會來到 循環長度 的位置，也是循環起點，兩者在此相遇。
手稿示意圖
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head: return head
        FastPointer, SlowPointer = head, head
        while 1:
            # SlwoPointer go 1 step forward
            SlowPointer = SlowPointer.next            
            # FastPointer go 2 steps forward
            if FastPointer.next and FastPointer.next.next:
                FastPointer = FastPointer.next.next
                if FastPointer == SlowPointer: break
            else:
                return None
        # FP SP meet in cycle(CycleLength - pos)
        SlowPointer = head
        while 1:
            if FastPointer == SlowPointer: return FastPointer
            SlowPointer = SlowPointer.next
            FastPointer = FastPointer.next
於
標籤： ,