Magic Loop - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Cycle Detection, Slow and Fast Pointer Technique

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 find the node where a cycle begins in a linked list, if such a cycle exists.
  • What approach can be used?
    • The slow and fast pointer technique can be used to detect the cycle and then determine the start of the cycle.
HAPPY CASE
Input: path_start = Node("Mystic Falls"), with subsequent nodes leading to a cycle starting at "Troll's Bridge"
Output: "Troll's Bridge"
Explanation: The linked list has a cycle that begins at "Troll's Bridge".

EDGE CASE
Input: path_start = None
Output: None
Explanation: An empty list has no cycle.

EDGE CASE
Input: path_start = Node("Mystic Falls"), with no cycle
Output: None
Explanation: A list with no cycle should return None.

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 and Cycle Start Determination, we want to consider the following approaches:

  • Two Pointers (Slow and Fast Pointer Technique): Use two pointers to first detect the cycle, and then determine the start of the cycle.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use the slow and fast pointer technique to first detect if a cycle exists. If a cycle is detected, we will then reset one pointer to the start of the list and move both pointers one step at a time until they meet, which will be the start of the cycle.

1) Initialize two pointers, slow and fast, both pointing to the head of the list.
2) Traverse the list with the following steps:
    a) Move the slow pointer by one step.
    b) Move the fast pointer by two steps.
    c) If slow and fast pointers meet, a cycle is detected.
3) If a cycle is detected:
    a) Reset one pointer (slow) to the start of the list.
    b) Move both pointers one step at a time.
    c) The point where they meet again is the start of the cycle.
4) If no cycle is detected, return None.

⚠️ Common Mistakes

  • Failing to handle edge cases, such as when the list is empty or contains only one node.
  • Incorrectly updating pointers during the second traversal, leading to incorrect results.

4: I-mplement

Implement the code to solve the algorithm.

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

# Function to find the start of the loop
def loop_start(path_start):
    if not path_start:
        return None

    slow = path_start
    fast = path_start

    # Step 1: Detect cycle using slow and fast pointers
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            # Step 2: Find the start of the cycle
            slow = path_start
            while slow != fast:
                slow = slow.next
                fast = fast.next

            return slow.value

    # No cycle found
    return None

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 path_start linked list to verify that the function correctly identifies the start of the cycle.

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 each node is visited at most twice.
  • Space Complexity: O(1) because the algorithm uses a constant amount of extra space for pointers.