Wild Goose Chase

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

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 15-25 mins
🛠️ Topics: Linked Lists, Cycle Detection

1: U-nderstand

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

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

What does the problem ask for?
- The problem asks to determine whether the tail of a linked list points back to the head, making the linked list circular.
What should be returned?
- The function should return True if the linked list is circular, otherwise 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 it is not circular in the sense asked for here, because the tail does not point back to the head. 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: clue1 = Node("The stolen goods are at an abandoned warehouse")
       clue2 = Node("The mayor is accepting bribes")
       clue3 = Node("They dumped their disguise in the lake")
       clue1.next = clue2
       clue2.next = clue3
       clue3.next = clue1  # Circular link
Output: True
Explanation: The linked list is circular because the last node points back to the head.

EDGE CASE
Input: clue1 = Node("The stolen goods are at an abandoned warehouse")
       clue2 = Node("The mayor is accepting bribes")
       clue3 = Node("They dumped their disguise in the lake")
       clue1.next = clue2
       clue2.next = clue3
       clue3.next = None  # Not circular
Output: False
Explanation: The linked list is not circular because the last node does not point back to the head.

EDGE CASE
Input: clue1 = Node("The stolen goods are at an abandoned warehouse")
       clue2 = Node("The mayor is accepting bribes")
       clue3 = Node("They dumped their disguise in the lake")
       clue1.next = clue2
       clue2.next = clue3
       clue3.next = clue2  # Tail links back to the middle, not the head
Output: False
Explanation: The list has a cycle (clue2 -> clue3 -> clue2), but the head clue1 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 Linked List problems involving Cycle Detection (Circularity Check), we want to consider the following approaches:

Floyd’s Cycle Detection Algorithm: Also known as the “Tortoise and Hare” algorithm. 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.
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 linked 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

Forgetting to handle the case where the list is empty.
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.
Treating any cycle as a circular list. A list whose tail links back to a middle node has a cycle, but the tail does not point back to the head, so the answer is False.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def is_circular(clues):
    if not clues:
        return False

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

    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 == clues:
            return True
        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.

Example: Use the provided clue1, clue2, and clue3 linked lists to verify that the function correctly identifies whether the list is circular.
- Happy case (clue3.next = clue1): slow/fast move to clue2/clue3, then clue3/clue2, then meet at clue1. The lap starts at clue1, which is the head, so the function returns True.
- First edge case (clue3.next = None): slow/fast move to clue2/clue3. Then fast.next is None, so the loop ends without a meeting and the function returns False.
- Second edge case (clue3.next = clue2): slow/fast move to clue2/clue3, then meet at clue3. The lap visits clue3, then clue2, then returns to clue3 without reaching clue1, so the function returns False.

6: E-valuate

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

Assume N represents the number of nodes in the linked list.

Time Complexity: O(N) 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) because the algorithm uses a constant amount of extra space for pointers.