Linked list cycle problems are a common topic in coding interviews, especially for tech giants like FAANG companies. These problems test a candidate’s understanding of data structures, algorithms, and problem-solving skills. In this comprehensive guide, we’ll explore various strategies to tackle linked list cycle problems, providing you with the tools you need to excel in your technical interviews and improve your overall coding prowess.

Table of Contents

  1. Introduction to Linked List Cycles
  2. Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)
  3. Hash Set Approach
  4. Linked List Modification Technique
  5. Finding the Length of the Cycle
  6. Detecting the Start of the Cycle
  7. Removing the Cycle
  8. Variations of Linked List Cycle Problems
  9. Optimization Techniques
  10. Practice Problems and Solutions
  11. Conclusion

1. Introduction to Linked List Cycles

Before diving into the strategies, let’s first understand what a linked list cycle is. A linked list cycle occurs when a node in the linked list points back to a previous node, creating a loop. This can happen in various scenarios and can lead to infinite traversal if not handled properly.

Here’s a simple representation of a linked list with a cycle:

1 -> 2 -> 3 -> 4 -> 5
         ^              |
         |              |
         ---------------

In this example, the last node (5) points back to node 2, creating a cycle.

Detecting and handling cycles in linked lists is crucial for several reasons:

  • Preventing infinite loops in algorithms that traverse linked lists
  • Identifying and fixing corrupted data structures
  • Optimizing memory usage by removing unnecessary cycles
  • Solving complex problems that involve cyclic relationships

Now that we understand the importance of dealing with linked list cycles, let’s explore various strategies to solve related problems.

2. Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)

Floyd’s Cycle-Finding Algorithm, also known as the “Tortoise and Hare” algorithm, is one of the most efficient and widely used methods for detecting cycles in linked lists. This algorithm uses two pointers moving at different speeds to determine if a cycle exists.

How it works:

  1. Initialize two pointers, slow and fast, both pointing to the head of the linked list.
  2. Move the slow pointer one step at a time and the fast pointer two steps at a time.
  3. If there’s a cycle, the fast pointer will eventually meet the slow pointer inside the cycle.
  4. If there’s no cycle, the fast pointer will reach the end of the list (null).

Here’s a Python implementation of Floyd’s algorithm:

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

def has_cycle(head):
    if not head or not head.next:
        return False
    
    slow = head
    fast = head.next
    
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    
    return True

Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), as we only use two pointers regardless of the list size.

Advantages:

  • Efficient space usage (constant space complexity)
  • Works well for large linked lists
  • Can be extended to find the start of the cycle and its length

Disadvantages:

  • Slightly more complex to implement compared to other methods
  • May take longer to detect cycles in very large lists with small cycles

3. Hash Set Approach

The Hash Set approach is a straightforward method to detect cycles in a linked list. It involves storing visited nodes in a hash set and checking if a node has been visited before.

How it works:

  1. Create an empty hash set to store visited nodes.
  2. Traverse the linked list, adding each node to the hash set.
  3. If a node is already in the hash set, a cycle is detected.
  4. If we reach the end of the list (null) without finding a duplicate, there’s no cycle.

Here’s a Python implementation of the Hash Set approach:

def has_cycle_hash_set(head):
    visited = set()
    current = head
    
    while current:
        if current in visited:
            return True
        visited.add(current)
        current = current.next
    
    return False

Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(n), as we store all nodes in the hash set in the worst case.

Advantages:

  • Simple to implement and understand
  • Can detect cycles quickly, especially in smaller lists
  • Useful when you need to keep track of visited nodes for other purposes

Disadvantages:

  • Higher space complexity compared to Floyd’s algorithm
  • May be less efficient for very large linked lists due to memory usage

4. Linked List Modification Technique

The Linked List Modification Technique involves temporarily modifying the linked list structure to detect cycles. This method is less common but can be useful in certain scenarios.

How it works:

  1. Traverse the linked list, modifying each node to point to a sentinel node.
  2. If we encounter a node that already points to the sentinel, a cycle is detected.
  3. After detection, restore the original list structure.

Here’s a Python implementation of the Linked List Modification Technique:

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

def has_cycle_modification(head):
    if not head:
        return False
    
    sentinel = ListNode(0)
    current = head
    
    while current:
        if current.next == sentinel:
            # Restore the list before returning
            restore_list(head, sentinel)
            return True
        
        next_node = current.next
        current.next = sentinel
        current = next_node
    
    # Restore the list before returning
    restore_list(head, sentinel)
    return False

def restore_list(head, sentinel):
    current = head
    while current and current.next == sentinel:
        current.next = current.next.next
        current = current.next

Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), as we only use a constant amount of extra space.

Advantages:

  • Constant space complexity
  • Can be useful when modification of the list is allowed

Disadvantages:

  • Temporarily modifies the original list structure
  • Requires careful implementation to ensure proper restoration
  • May not be suitable for concurrent environments or when the list shouldn’t be modified

5. Finding the Length of the Cycle

Once a cycle is detected, you might need to find its length. This can be achieved by extending Floyd’s algorithm or using a separate technique.

Method using Floyd’s algorithm:

  1. Use Floyd’s algorithm to detect the cycle and find the meeting point.
  2. Keep one pointer at the meeting point and move the other pointer until they meet again.
  3. Count the steps taken for the second meeting to find the cycle length.

Here’s a Python implementation to find the cycle length:

def find_cycle_length(head):
    if not head or not head.next:
        return 0
    
    # Detect cycle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return 0  # No cycle found
    
    # Find cycle length
    current = slow.next
    length = 1
    while current != slow:
        current = current.next
        length += 1
    
    return length

Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), as we only use a constant amount of extra space.

6. Detecting the Start of the Cycle

Detecting the start node of a cycle is another common problem. This can be solved efficiently using Floyd’s algorithm with an additional step.

How it works:

  1. Use Floyd’s algorithm to detect the cycle and find the meeting point.
  2. Reset one pointer to the head of the list.
  3. Move both pointers one step at a time until they meet again.
  4. The meeting point is the start of the cycle.

Here’s a Python implementation to find the start of the cycle:

def find_cycle_start(head):
    if not head or not head.next:
        return None
    
    # Detect cycle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle found
    
    # Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow  # This is the start of the cycle

Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), as we only use a constant amount of extra space.

7. Removing the Cycle

In some cases, you might need to remove the cycle from a linked list. This can be done by finding the last node of the cycle and setting its next pointer to null.

Steps to remove the cycle:

  1. Detect the cycle using Floyd’s algorithm.
  2. Find the start of the cycle.
  3. Traverse the cycle to find the last node.
  4. Set the last node’s next pointer to null.

Here’s a Python implementation to remove the cycle:

def remove_cycle(head):
    if not head or not head.next:
        return
    
    # Detect cycle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return  # No cycle found
    
    # Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    # Find last node of the cycle
    while fast.next != slow:
        fast = fast.next
    
    # Remove the cycle
    fast.next = None

Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), as we only use a constant amount of extra space.

8. Variations of Linked List Cycle Problems

Linked list cycle problems can come in various forms. Here are some common variations you might encounter in coding interviews:

8.1. Detect Cycle in a Circular Linked List

In this variation, you need to determine if a given linked list is circular (i.e., the last node points back to the first node).

def is_circular(head):
    if not head:
        return False
    
    current = head.next
    while current and current != head:
        current = current.next
    
    return current == head

8.2. Find the Middle Node of a Linked List with a Cycle

This problem involves finding the middle node of a linked list that may contain a cycle.

def find_middle_with_cycle(head):
    if not head or not head.next:
        return head
    
    # Detect cycle
    slow = fast = head
    has_cycle = False
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break
    
    if not has_cycle:
        # No cycle, use regular method to find middle
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    # Count nodes in the cycle
    cycle_length = 1
    fast = fast.next
    while fast != slow:
        cycle_length += 1
        fast = fast.next
    
    # Find total length of the list
    total_length = cycle_length
    current = head
    while current != slow:
        total_length += 1
        current = current.next
    
    # Find middle node
    middle = head
    for _ in range(total_length // 2):
        middle = middle.next
    
    return middle

8.3. Determine if Two Linked Lists Intersect (with Possible Cycles)

This problem involves determining if two linked lists intersect, considering that either or both lists may contain cycles.

def get_intersection_node(headA, headB):
    def detect_cycle(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return slow
        return None
    
    def get_cycle_length(meeting_point):
        current = meeting_point
        length = 0
        while True:
            current = current.next
            length += 1
            if current == meeting_point:
                return length
    
    # Detect cycles in both lists
    cycle_a = detect_cycle(headA)
    cycle_b = detect_cycle(headB)
    
    # Case 1: Both lists are acyclic
    if not cycle_a and not cycle_b:
        # Use the regular intersection method for acyclic lists
        return find_intersection_acyclic(headA, headB)
    
    # Case 2: One list is cyclic, the other is acyclic
    if (cycle_a and not cycle_b) or (cycle_b and not cycle_a):
        return None
    
    # Case 3: Both lists are cyclic
    if cycle_a == cycle_b:
        # The cycles are the same, find the intersection point
        return find_intersection_cyclic(headA, headB, cycle_a)
    
    # Case 4: Both lists have different cycles
    current = cycle_a.next
    while current != cycle_a:
        if current == cycle_b:
            # The cycles intersect
            return cycle_a
        current = current.next
    
    # The cycles do not intersect
    return None

def find_intersection_acyclic(headA, headB):
    if not headA or not headB:
        return None
    
    ptrA, ptrB = headA, headB
    while ptrA != ptrB:
        ptrA = ptrA.next if ptrA else headB
        ptrB = ptrB.next if ptrB else headA
    
    return ptrA

def find_intersection_cyclic(headA, headB, cycle_start):
    ptrA, ptrB = headA, headB
    while ptrA != ptrB:
        ptrA = ptrA.next if ptrA != cycle_start else headB
        ptrB = ptrB.next if ptrB != cycle_start else headA
    
    return ptrA

9. Optimization Techniques

When solving linked list cycle problems, consider these optimization techniques to improve your solutions:

9.1. Early Termination

In some cases, you can terminate the algorithm early if certain conditions are met. For example, in Floyd’s algorithm, you can return false as soon as the fast pointer reaches the end of the list.

9.2. Handling Edge Cases

Always consider edge cases such as empty lists, single-node lists, or lists with only two nodes. Handling these cases early can improve the efficiency and robustness of your code.

9.3. Combining Algorithms

Sometimes, combining multiple algorithms can lead to more efficient solutions. For example, you can use Floyd’s algorithm to detect a cycle and then use the hash set approach to find the start of the cycle if memory usage is not a concern.

9.4. Bit Manipulation

In some cases, using bit manipulation techniques can optimize space usage. For example, you can use the least significant bit of the node’s memory address to mark visited nodes instead of using a separate hash set.

10. Practice Problems and Solutions

To reinforce your understanding of linked list cycle problems, here are some practice problems with their solutions:

Problem 1: Linked List Cycle II (LeetCode 142)

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return None
        
        # Detect cycle
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        else:
            return None  # No cycle found
        
        # Find cycle start
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        return slow

Problem 2: Intersection of Two Linked Lists (LeetCode 160)

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        
        ptrA, ptrB = headA, headB
        while ptrA != ptrB:
            ptrA = ptrA.next if ptrA else headB
            ptrB = ptrB.next if ptrB else headA
        
        return ptrA

Problem 3: Happy Number (LeetCode 202)

Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy numbers.
class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(num):
            return sum(int(d)**2 for d in str(num))
        
        slow = fast = n
        while True:
            slow = get_next(slow)
            fast = get_next(get_next(fast))
            if slow == fast:
                break
        
        return slow == 1

11. Conclusion

Mastering linked list cycle problems is crucial for success in coding interviews, especially when aiming for positions at top tech companies. By understanding and practicing the strategies outlined in this guide, you’ll be well-equipped to tackle a wide range of linked list cycle problems.

Remember to:

  • Start with the fundamentals, such as Floyd’s Cycle-Finding Algorithm and the Hash Set approach.
  • Practice identifying and implementing the most suitable strategy for each problem.
  • Consider optimization techniques to improve your solutions.
  • Regularly practice with varied problems to reinforce your skills.

As you continue to hone your skills in solving linked list cycle problems, you’ll find that these techniques can be applied to a wide range of other data structure and algorithm challenges. Keep practicing, and you’ll be well on your way to acing your technical interviews and becoming a more proficient programmer.