142. Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii

Python

While Loop

Space O(N)

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        memory = set()

        node = head
        n = 0

        while node and id(node) not in memory:
            memory.add(id(node))
            node = node.next
            n += 1

        if not node:
            return

        return node

Two Pointer

Floyd's Tortoise and Hare Algorithm

Solution from here

Space O(1)

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return
        first = True

        slow, fast = head, head

        while slow != fast or first:
            first = False
            if not fast or not fast.next:
                return
            slow = slow.next
            fast = fast.next.next


        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return fast