algoadvance

Given the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

Clarifying Questions:

1. What should be the return type?
   • The function should return a boolean value: True if a cycle is detected, False otherwise.
2. Should we handle empty linked list cases?
   • Yes, if the linked list is empty (head is None), the function should return False.
3. What is the structure of a linked list node?
   • Each node in the list contains a value (val) and a pointer (next) to the next node.

Strategy:

We will use Floyd’s Cycle-Finding Algorithm (also known as the Tortoise and Hare Algorithm):

1. Initialize Two Pointers: Initialize two pointers, both starting from the head of the linked list. The fast pointer (hare) will move two steps at a time, while the slow pointer (tortoise) will move one step at a time.

2. Move the Pointers: In each iteration, advance the slow pointer by one step and the fast pointer by two steps.

3. Check for Cycle: If there is a cycle, the fast pointer will eventually meet the slow pointer. If the fast pointer reaches the end of the list (None), then there is no cycle.

4. Return Result: If the fast pointer meets the slow pointer, return True indicating a cycle exists. Otherwise, if the fast pointer reaches the end, return False.

Code:

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

def hasCycle(head: ListNode) -> bool:
    if not head:
        return False

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

Time Complexity:

• Time Complexity: O(n), where n is the number of nodes in the linked list. In the worst case, we will traverse each node once.
• Space Complexity: O(1), as we only use two pointers and no additional data structures that scale with the input size.

This solution effectively detects cycles using constant space and linear time.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?