LC 141

Solutions to LeetCode 141 Linked List Cycle.

LeetCode 141

Linked List Cycle (Easy) [link]

1. Iterate through all nodes and determine whether this node is visited before. We use HashTable to store the nodes visited. Set is sufficient to store the information about whether a node is visited.

   Time complexity O(n), space complexity O(n).

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        visited = set()
        while head:
            if head in visited:
                return True
            visited.add(head)
            head = head.next
        return False

2. Fast and slow pointers.

   If the fast pointer catches up the slow pointer from behind, there must be a cycle.

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                return True
        return False