Detect Circular Linked List

TIP101 Unit 6 Session 2 (Click for link to problem statements)

Problem Highlights

💡 Difficulty: Easy
⏰ Time to complete: 15 mins
🛠️ Topics: Linked Lists

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

What if the linked list only contains one node?
- If the single node points to itself, the function should return True; otherwise, it should return False.
What if the linked list is empty?
- An empty list is not circular by definition so the function should return False.
What if the tail links back to a node in the middle of the list instead of the head?
- That list contains a cycle, but the tail does not point back to the head, so following this page’s definition the function should return False. The function must still terminate on this input, because following next pointers never reaches None and never reaches the head again.

HAPPY CASE
Input: A list where the last node points back to the first node (e.g., num1 -> num2 -> num3 -> num1)
Output: True
Explanation: The tail node points back to the head, forming a circular linked list.

EDGE CASE
Input: A single node that does not point to itself (e.g., num1)
Output: False
Explanation: The single node points to None, indicating it is not a circular linked list.

EDGE CASE
Input: A list whose tail points back to a middle node (e.g., num1 -> num2 -> num3 -> num2)
Output: False
Explanation: The list has a cycle (num2 -> num3 -> num2), but the head num1 is not on it, so the tail does not point back to the head.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Circular Linked List detection problems, we want to consider the following approaches:

Floyd’s Cycle Detection Algorithm (“Tortoise and Hare”): a slow pointer moves one step and a fast pointer moves two steps at a time. They meet only if the list has a cycle, and the fast pointer reaches None if it does not. A circular linked list should not have any node pointing to None.
Traversal: Once a cycle is found, walk one lap around it to check whether the head is on the cycle. The tail points back to the head exactly when the head is part of the cycle.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: A plain traversal that stops only at None or at the head never finishes when the tail links back to a middle node. So we first use Floyd’s Cycle Detection Algorithm to decide whether there is any cycle at all. If there is, we walk one lap around the cycle from the meeting point. The list is circular only if that lap passes through the head.

1) If the list is empty, return False.
2) Use Floyd's Cycle Detection Algorithm to detect if there is a cycle:
    a) Initialize two pointers, `slow` and `fast`, both pointing to the head of the list.
    b) Move `slow` by one step and `fast` by two steps.
    c) If `slow` meets `fast`, a cycle is detected.
    d) If `fast` reaches the end of the list, there is no cycle, so return False.
3) Walk one lap around the cycle, starting from the meeting point:
    a) If the current node is the head of the list, return True (the tail points back to the head).
    b) Move to the next node.
    c) If we are back at the meeting point, the head is not on the cycle, so return False.

⚠️ Common Mistakes

Not handling the empty list case.
Assuming the list either ends in None or loops back to the head. If the tail links back to a middle node, a loop that only stops at None or at the head runs forever.

4: I-mplement

Implement the code to solve the algorithm.

def is_circular(head):
    if not head:
        return False  # An empty list is not circular by definition

    # Step 1: Detect a cycle using Floyd's Cycle Detection Algorithm
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        # fast reached the end of the list, so there is no cycle
        return False

    # Step 2: Walk one lap around the cycle; the list is circular only if the head is on it
    current = slow
    while True:
        if current == head:
            return True  # Found that tail points back to head
        current = current.next
        if current == slow:
            return False

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

Happy case (num1 -> num2 -> num3 -> num1): slow/fast move to num2/num3, then num3/num2, then meet at num1. The lap starts at num1, which is the head, so the function returns True.
Edge case (single node num1 pointing to None): fast.next is None, so the loop ends without a meeting and the function returns False.
Single node pointing to itself: slow and fast both move back to num1 and meet there. The lap starts at the head, so the function returns True.
Edge case (num1 -> num2 -> num3 -> num2): slow/fast move to num2/num3, then meet at num3. The lap visits num3, then num2, then returns to num3 without reaching num1, so the function returns False.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity: O(n) where n is the number of nodes in the linked list, because the algorithm makes O(n) total pointer moves. Without a cycle, fast reaches the end after about n / 2 iterations. With a cycle, slow takes at most n steps before the two pointers meet, and the second phase walks one lap of the cycle, which has at most n nodes.
Space Complexity: O(1) as no extra space is used other than a few variables for tracking nodes.