Solution 1 - Hash Set

Traverse the linked list and store each visited node in a set. For each node, check if it already exists in the set. If it does, a cycle is detected. If we reach the end of the list (None), there is no cycle.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0141.1 - Linked List Cycle - Solution 1 - Hash Set """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class ListNode:
    """ListNode Class"""

    def __init__(self, x: int):
        self.val = x
        self.next = None


class Solution:
    """Solution Class"""

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        """Linked List Cycle Function"""
        seen = set()

        current = head
        while current:
            if current in seen:
                return True
            seen.add(current)
            current = current.next

        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Test 1: [3,2,0,-4] with cycle at pos 1
    n1 = ListNode(3)
    n2 = ListNode(2)
    n3 = ListNode(0)
    n4 = ListNode(-4)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n2
    print(Solution().hasCycle(n1))  # True

    # Test 2: [1,2] with cycle at pos 0
    a1 = ListNode(1)
    a2 = ListNode(2)
    a1.next = a2
    a2.next = a1
    print(Solution().hasCycle(a1))  # True

    # Test 3: [1] with no cycle
    b1 = ListNode(1)
    print(Solution().hasCycle(b1))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Floyd's Tortoise and Hare

Use two pointers moving at different speeds. The slow pointer moves one step at a time, while the fast pointer moves two steps. If a cycle exists, the fast pointer will eventually catch up to the slow pointer. If the fast pointer reaches the end, there is no cycle.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0141.2 - Linked List Cycle - Solution 2 - Floyd's Tortoise and Hare """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class ListNode:
    """ListNode Class"""

    def __init__(self, x: int):
        self.val = x
        self.next = None


class Solution:
    """Solution Class"""

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        """Linked List Cycle Function"""
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True

        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Test 1: [3,2,0,-4] with cycle at pos 1
    n1 = ListNode(3)
    n2 = ListNode(2)
    n3 = ListNode(0)
    n4 = ListNode(-4)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n2
    print(Solution().hasCycle(n1))  # True

    # Test 2: [1,2] with cycle at pos 0
    a1 = ListNode(1)
    a2 = ListNode(2)
    a1.next = a2
    a2.next = a1
    print(Solution().hasCycle(a1))  # True

    # Test 3: [1] with no cycle
    b1 = ListNode(1)
    print(Solution().hasCycle(b1))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0141 - Linked List Cycle

Solution 1 - Hash Set

Solution 2 - Floyd's Tortoise and Hare