Linked List Cycle

TARGET DECK: Leetcode FILE TAGS: Easy

---

Intuition

• Slow and Steady beats the race
• Be careful about making sure the tortoise and the hare start out in different locations.

Cards

START Basic Front: Linked List Cycle Back: Use Floyds Tortoise and Hare with count variable.

END

Complexity

Runtime

$O(N)$, since the slow pointer moves N times, and the fast pointer moves at most N times, before heading into a cycle in which it takes ()()()

Todo

Need to analyze why it takes $O(N)$. My intuitive understanding is that there are less than N elements in the cycle, but I don’t get it since I had tried solving a similar question Find the Duplicate Number by using the same algorithm found here, but found that it looped for quite a long time. i.e. I tried to get the algorithm to go up by 2 indices at a time, but this was bound by N()()().

Space

$O(1)$

Code

Simplified Tortoise and Hare

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        tortoise = hare = head
        count = 0
        while hare:
            count += 1
            hare = hare.next
            if count % 2 == 0:
                tortoise = tortoise.next
            if tortoise == hare:
                return True
        return False

Tortoise and Hare

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        if not head.next:
            return False
 
        tortoise = head
        hare = head.next
 
        count = 0
        while tortoise != hare:
            if not hare:
                return False
                
            count += 1
            if count % 2 == 0:
                tortoise = tortoise.next
            hare = hare.next
 
        return True

No Count Just Tortoise and Hare

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
 
        tortoise, hare = head, head
        while tortoise and hare:
            if not hare.next:
                return False
            hare = hare.next
            tortoise = tortoise.next
            if not hare.next:
                return False
            hare = hare.next
            if tortoise == hare:
                return True
        return False

Using $O(N)$ Space

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Assuming: node vals are unique
        if not head:
            return False
        if not head.next:
            return False
        
        my_set = set()
        my_set.add(head)
        
        while head.next:
            if head.next in my_set:
                return True
            
            my_set.add(head.next)
            head = head.next
        
        return False

Notes

---

References

• Linked List Cycle