[Leetcode] 142. Linked List Cycle II

問題のショートカット
Hash Set
Time Complexity: O(n)O(n)O(n)
Space Complexity: O(n)O(n)O(n)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        nodeSet = set()
        while head:
            if head in nodeSet:
                return head
            nodeSet.add(head)
            head = head.next
        return None

Floyd cycle detection
fast移動速度がslowの2倍であることから,ループを開始するノードを見つけることができる.
1~9の値で,4~9にループが存在するノードが1つあるとする.
1-->2-->3-->4-->5-->6-->7-->8-->9-->Back to 4
|<-----xxx----->|<---yyy--->|<--------zzz-------->|
slowとfastは6で出会うが,このときそれぞれ移動するノード数は以下のようになる.

slow: x+yx+yx+y

fast: x+y+z+y=x+2y+zx+y+z+y = x+2y+zx+y+z+y=x+2y+z

fastの移動個数はslowの2倍であるため、以下の意識を形成する.
2(x+y)=x+2y+z2(x+y) = x+2y+z2(x+y)=x+2y+z
2x=x+z2x = x+z2x=x+z
x=zx = zx=z
Z=xz=xz=xなので、fastはFloydループ検出を終了した点x+yx+yx+yで、2番目のノードで再度xxxを移動すればよい.linked listはインデックスナビゲーションができないため、headアドレスをslow変数に再割り当てしてxxxの移動を支援します.
これは1格移動ごとに遅い=fastの点です.
Time Complexity: O(n)O(n)O(n)
Space Complexity: O(1)O(1)O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return None
        fast, slow = head.next.next, head.next
        
        # detect cycle
        while slow != fast:
            slow = slow.next
            try:
                fast = fast.next.next
            except AttributeError:
                return None
        
        # find the node that a cycle starts
        slow = head
        while slow != fast:
            fast = fast.next
            slow = slow.next
        return slow

コメントとソース

Explanation for dumb people like me, FYI the fast pointer does not travel a distance 2X+2Y directly - ショートカット