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.<\/p>\n

Table of Contents<\/h2>\n

1. Introduction to Linked List Cycles<\/h2>\n

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.<\/p>\n

Here’s a simple representation of a linked list with a cycle:<\/p>\n

1 -> 2 -> 3 -> 4 -> 5\n         ^              |\n         |              |\n         ---------------<\/code><\/pre>\nIn this example, the last node (5) points back to node 2, creating a cycle.<\/p>\n
Detecting and handling cycles in linked lists is crucial for several reasons:<\/p>\n
\nPreventing infinite loops in algorithms that traverse linked lists<\/li>\n
Identifying and fixing corrupted data structures<\/li>\n
Optimizing memory usage by removing unnecessary cycles<\/li>\n
Solving complex problems that involve cyclic relationships<\/li>\n<\/ul>\nNow that we understand the importance of dealing with linked list cycles, let’s explore various strategies to solve related problems.<\/p>\n
2. Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)<\/h2>\nFloyd’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.<\/p>\n
How it works:<\/h3>\n\nInitialize two pointers, slow and fast, both pointing to the head of the linked list.<\/li>\n
Move the slow pointer one step at a time and the fast pointer two steps at a time.<\/li>\n
If there’s a cycle, the fast pointer will eventually meet the slow pointer inside the cycle.<\/li>\n
If there’s no cycle, the fast pointer will reach the end of the list (null).<\/li>\n<\/ol>\nHere’s a Python implementation of Floyd’s algorithm:<\/p>\n
class ListNode:\n    def __init__(self, val=0, next=None):\n        self.val = val\n        self.next = next\n\ndef has_cycle(head):\n    if not head or not head.next:\n        return False\n    \n    slow = head\n    fast = head.next\n    \n    while slow != fast:\n        if not fast or not fast.next:\n            return False\n        slow = slow.next\n        fast = fast.next.next\n    \n    return True<\/code><\/pre>\nTime Complexity: O(n), where n is the number of nodes in the linked list.
\n  Space Complexity: O(1), as we only use two pointers regardless of the list size.<\/p>\n
Advantages:<\/h3>\n\nEfficient space usage (constant space complexity)<\/li>\n
Works well for large linked lists<\/li>\n
Can be extended to find the start of the cycle and its length<\/li>\n<\/ul>\nDisadvantages:<\/h3>\n\nSlightly more complex to implement compared to other methods<\/li>\n
May take longer to detect cycles in very large lists with small cycles<\/li>\n<\/ul>\n3. Hash Set Approach<\/h2>\nThe 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.<\/p>\n
How it works:<\/h3>\n\nCreate an empty hash set to store visited nodes.<\/li>\n
Traverse the linked list, adding each node to the hash set.<\/li>\n
If a node is already in the hash set, a cycle is detected.<\/li>\n
If we reach the end of the list (null) without finding a duplicate, there’s no cycle.<\/li>\n<\/ol>\nHere’s a Python implementation of the Hash Set approach:<\/p>\n
def has_cycle_hash_set(head):\n    visited = set()\n    current = head\n    \n    while current:\n        if current in visited:\n            return True\n        visited.add(current)\n        current = current.next\n    \n    return False<\/code><\/pre>\nTime Complexity: O(n), where n is the number of nodes in the linked list.
\n  Space Complexity: O(n), as we store all nodes in the hash set in the worst case.<\/p>\n
Advantages:<\/h3>\n\nSimple to implement and understand<\/li>\n
Can detect cycles quickly, especially in smaller lists<\/li>\n
Useful when you need to keep track of visited nodes for other purposes<\/li>\n<\/ul>\nDisadvantages:<\/h3>\n\nHigher space complexity compared to Floyd’s algorithm<\/li>\n
May be less efficient for very large linked lists due to memory usage<\/li>\n<\/ul>\n4. Linked List Modification Technique<\/h2>\nThe 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.<\/p>\n
How it works:<\/h3>\n\nTraverse the linked list, modifying each node to point to a sentinel node.<\/li>\n
If we encounter a node that already points to the sentinel, a cycle is detected.<\/li>\n
After detection, restore the original list structure.<\/li>\n<\/ol>\nHere’s a Python implementation of the Linked List Modification Technique:<\/p>\n
class ListNode:\n    def __init__(self, val=0, next=None):\n        self.val = val\n        self.next = next\n\ndef has_cycle_modification(head):\n    if not head:\n        return False\n    \n    sentinel = ListNode(0)\n    current = head\n    \n    while current:\n        if current.next == sentinel:\n            # Restore the list before returning\n            restore_list(head, sentinel)\n            return True\n        \n        next_node = current.next\n        current.next = sentinel\n        current = next_node\n    \n    # Restore the list before returning\n    restore_list(head, sentinel)\n    return False\n\ndef restore_list(head, sentinel):\n    current = head\n    while current and current.next == sentinel:\n        current.next = current.next.next\n        current = current.next<\/code><\/pre>\nTime Complexity: O(n), where n is the number of nodes in the linked list.
\n  Space Complexity: O(1), as we only use a constant amount of extra space.<\/p>\n
Advantages:<\/h3>\n\nConstant space complexity<\/li>\n
Can be useful when modification of the list is allowed<\/li>\n<\/ul>\nDisadvantages:<\/h3>\n\nTemporarily modifies the original list structure<\/li>\n
Requires careful implementation to ensure proper restoration<\/li>\n
May not be suitable for concurrent environments or when the list shouldn’t be modified<\/li>\n<\/ul>\n5. Finding the Length of the Cycle<\/h2>\nOnce 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.<\/p>\n
Method using Floyd’s algorithm:<\/h3>\n\nUse Floyd’s algorithm to detect the cycle and find the meeting point.<\/li>\n
Keep one pointer at the meeting point and move the other pointer until they meet again.<\/li>\n
Count the steps taken for the second meeting to find the cycle length.<\/li>\n<\/ol>\nHere’s a Python implementation to find the cycle length:<\/p>\n
def find_cycle_length(head):\n    if not head or not head.next:\n        return 0\n    \n    # Detect cycle\n    slow = fast = head\n    while fast and fast.next:\n        slow = slow.next\n        fast = fast.next.next\n        if slow == fast:\n            break\n    else:\n        return 0  # No cycle found\n    \n    # Find cycle length\n    current = slow.next\n    length = 1\n    while current != slow:\n        current = current.next\n        length += 1\n    \n    return length<\/code><\/pre>\nTime Complexity: O(n), where n is the number of nodes in the linked list.
\n  Space Complexity: O(1), as we only use a constant amount of extra space.<\/p>\n
6. Detecting the Start of the Cycle<\/h2>\nDetecting the start node of a cycle is another common problem. This can be solved efficiently using Floyd’s algorithm with an additional step.<\/p>\n
How it works:<\/h3>\n\nUse Floyd’s algorithm to detect the cycle and find the meeting point.<\/li>\n
Reset one pointer to the head of the list.<\/li>\n
Move both pointers one step at a time until they meet again.<\/li>\n
The meeting point is the start of the cycle.<\/li>\n<\/ol>\nHere’s a Python implementation to find the start of the cycle:<\/p>\n
def find_cycle_start(head):\n    if not head or not head.next:\n        return None\n    \n    # Detect cycle\n    slow = fast = head\n    while fast and fast.next:\n        slow = slow.next\n        fast = fast.next.next\n        if slow == fast:\n            break\n    else:\n        return None  # No cycle found\n    \n    # Find cycle start\n    slow = head\n    while slow != fast:\n        slow = slow.next\n        fast = fast.next\n    \n    return slow  # This is the start of the cycle<\/code><\/pre>\nTime Complexity: O(n), where n is the number of nodes in the linked list.
\n  Space Complexity: O(1), as we only use a constant amount of extra space.<\/p>\n
7. Removing the Cycle<\/h2>\nIn 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.<\/p>\n
Steps to remove the cycle:<\/h3>\n\nDetect the cycle using Floyd’s algorithm.<\/li>\n
Find the start of the cycle.<\/li>\n
Traverse the cycle to find the last node.<\/li>\n
Set the last node’s next pointer to null.<\/li>\n<\/ol>\nHere’s a Python implementation to remove the cycle:<\/p>\n
def remove_cycle(head):\n    if not head or not head.next:\n        return\n    \n    # Detect cycle\n    slow = fast = head\n    while fast and fast.next:\n        slow = slow.next\n        fast = fast.next.next\n        if slow == fast:\n            break\n    else:\n        return  # No cycle found\n    \n    # Find cycle start\n    slow = head\n    while slow != fast:\n        slow = slow.next\n        fast = fast.next\n    \n    # Find last node of the cycle\n    while fast.next != slow:\n        fast = fast.next\n    \n    # Remove the cycle\n    fast.next = None<\/code><\/pre>\nTime Complexity: O(n), where n is the number of nodes in the linked list.
\n  Space Complexity: O(1), as we only use a constant amount of extra space.<\/p>\n
8. Variations of Linked List Cycle Problems<\/h2>\nLinked list cycle problems can come in various forms. Here are some common variations you might encounter in coding interviews:<\/p>\n
8.1. Detect Cycle in a Circular Linked List<\/h3>\nIn this variation, you need to determine if a given linked list is circular (i.e., the last node points back to the first node).<\/p>\n
def is_circular(head):\n    if not head:\n        return False\n    \n    current = head.next\n    while current and current != head:\n        current = current.next\n    \n    return current == head<\/code><\/pre>\n8.2. Find the Middle Node of a Linked List with a Cycle<\/h3>\nThis problem involves finding the middle node of a linked list that may contain a cycle.<\/p>\n
def find_middle_with_cycle(head):\n    if not head or not head.next:\n        return head\n    \n    # Detect cycle\n    slow = fast = head\n    has_cycle = False\n    while fast and fast.next:\n        slow = slow.next\n        fast = fast.next.next\n        if slow == fast:\n            has_cycle = True\n            break\n    \n    if not has_cycle:\n        # No cycle, use regular method to find middle\n        slow = fast = head\n        while fast and fast.next:\n            slow = slow.next\n            fast = fast.next.next\n        return slow\n    \n    # Count nodes in the cycle\n    cycle_length = 1\n    fast = fast.next\n    while fast != slow:\n        cycle_length += 1\n        fast = fast.next\n    \n    # Find total length of the list\n    total_length = cycle_length\n    current = head\n    while current != slow:\n        total_length += 1\n        current = current.next\n    \n    # Find middle node\n    middle = head\n    for _ in range(total_length \/\/ 2):\n        middle = middle.next\n    \n    return middle<\/code><\/pre>\n8.3. Determine if Two Linked Lists Intersect (with Possible Cycles)<\/h3>\nThis problem involves determining if two linked lists intersect, considering that either or both lists may contain cycles.<\/p>\n
def get_intersection_node(headA, headB):\n    def detect_cycle(head):\n        slow = fast = head\n        while fast and fast.next:\n            slow = slow.next\n            fast = fast.next.next\n            if slow == fast:\n                return slow\n        return None\n    \n    def get_cycle_length(meeting_point):\n        current = meeting_point\n        length = 0\n        while True:\n            current = current.next\n            length += 1\n            if current == meeting_point:\n                return length\n    \n    # Detect cycles in both lists\n    cycle_a = detect_cycle(headA)\n    cycle_b = detect_cycle(headB)\n    \n    # Case 1: Both lists are acyclic\n    if not cycle_a and not cycle_b:\n        # Use the regular intersection method for acyclic lists\n        return find_intersection_acyclic(headA, headB)\n    \n    # Case 2: One list is cyclic, the other is acyclic\n    if (cycle_a and not cycle_b) or (cycle_b and not cycle_a):\n        return None\n    \n    # Case 3: Both lists are cyclic\n    if cycle_a == cycle_b:\n        # The cycles are the same, find the intersection point\n        return find_intersection_cyclic(headA, headB, cycle_a)\n    \n    # Case 4: Both lists have different cycles\n    current = cycle_a.next\n    while current != cycle_a:\n        if current == cycle_b:\n            # The cycles intersect\n            return cycle_a\n        current = current.next\n    \n    # The cycles do not intersect\n    return None\n\ndef find_intersection_acyclic(headA, headB):\n    if not headA or not headB:\n        return None\n    \n    ptrA, ptrB = headA, headB\n    while ptrA != ptrB:\n        ptrA = ptrA.next if ptrA else headB\n        ptrB = ptrB.next if ptrB else headA\n    \n    return ptrA\n\ndef find_intersection_cyclic(headA, headB, cycle_start):\n    ptrA, ptrB = headA, headB\n    while ptrA != ptrB:\n        ptrA = ptrA.next if ptrA != cycle_start else headB\n        ptrB = ptrB.next if ptrB != cycle_start else headA\n    \n    return ptrA<\/code><\/pre>\n9. Optimization Techniques<\/h2>\nWhen solving linked list cycle problems, consider these optimization techniques to improve your solutions:<\/p>\n
9.1. Early Termination<\/h3>\nIn 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.<\/p>\n
9.2. Handling Edge Cases<\/h3>\nAlways 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.<\/p>\n
9.3. Combining Algorithms<\/h3>\nSometimes, 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.<\/p>\n
9.4. Bit Manipulation<\/h3>\nIn 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.<\/p>\n
10. Practice Problems and Solutions<\/h2>\nTo reinforce your understanding of linked list cycle problems, here are some practice problems with their solutions:<\/p>\n
Problem 1: Linked List Cycle II (LeetCode 142)<\/h3>\nGiven the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.<\/p>\n
class Solution:\n    def detectCycle(self, head: ListNode) -> ListNode:\n        if not head or not head.next:\n            return None\n        \n        # Detect cycle\n        slow = fast = head\n        while fast and fast.next:\n            slow = slow.next\n            fast = fast.next.next\n            if slow == fast:\n                break\n        else:\n            return None  # No cycle found\n        \n        # Find cycle start\n        slow = head\n        while slow != fast:\n            slow = slow.next\n            fast = fast.next\n        \n        return slow<\/code><\/pre>\nProblem 2: Intersection of Two Linked Lists (LeetCode 160)<\/h3>\nGiven 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.<\/p>\n
class Solution:\n    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n        if not headA or not headB:\n            return None\n        \n        ptrA, ptrB = headA, headB\n        while ptrA != ptrB:\n            ptrA = ptrA.next if ptrA else headB\n            ptrB = ptrB.next if ptrB else headA\n        \n        return ptrA<\/code><\/pre>\nProblem 3: Happy Number (LeetCode 202)<\/h3>\nWrite an algorithm to determine if a number n is happy. A happy number is a number defined by the following process:<\/p>\n
\nStarting with any positive integer, replace the number by the sum of the squares of its digits.<\/li>\n
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.<\/li>\n
Those numbers for which this process ends in 1 are happy numbers.<\/li>\n<\/ul>\nclass Solution:\n    def isHappy(self, n: int) -> bool:\n        def get_next(num):\n            return sum(int(d)**2 for d in str(num))\n        \n        slow = fast = n\n        while True:\n            slow = get_next(slow)\n            fast = get_next(get_next(fast))\n            if slow == fast:\n                break\n        \n        return slow == 1<\/code><\/pre>\n11. Conclusion<\/h2>\nMastering 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.<\/p>\n
Remember to:<\/p>\n
\nStart with the fundamentals, such as Floyd’s Cycle-Finding Algorithm and the Hash Set approach.<\/li>\n
Practice identifying and implementing the most suitable strategy for each problem.<\/li>\n
Consider optimization techniques to improve your solutions.<\/li>\n
Regularly practice with varied problems to reinforce your skills.<\/li>\n<\/ul>\nAs 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.<\/p>\n<\/article>\n
<\/body><\/html><\/p>\n","protected":false},"excerpt":{"rendered":"
Linked list cycle problems are a common topic in coding interviews, especially for tech giants like FAANG companies. These problems…<\/p>\n","protected":false},"author":1,"featured_media":6095,"comment_status":"","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-6096","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/6096"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=6096"}],"version-history":[{"count":0,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/6096\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/6095"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=6096"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=6096"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=6096"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

3. Hash Set Approach<\/h2>\n
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.<\/p>\n

4. Linked List Modification Technique<\/h2>\n
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.<\/p>\n

5. Finding the Length of the Cycle<\/h2>\n
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.<\/p>\n

6. Detecting the Start of the Cycle<\/h2>\n
Detecting the start node of a cycle is another common problem. This can be solved efficiently using Floyd’s algorithm with an additional step.<\/p>\n

7. Removing the Cycle<\/h2>\n
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.<\/p>\n

8. Variations of Linked List Cycle Problems<\/h2>\n
Linked list cycle problems can come in various forms. Here are some common variations you might encounter in coding interviews:<\/p>\n

9. Optimization Techniques<\/h2>\n
When solving linked list cycle problems, consider these optimization techniques to improve your solutions:<\/p>\n

9.1. Early Termination<\/h3>\n
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.<\/p>\n

9.2. Handling Edge Cases<\/h3>\n
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.<\/p>\n

9.3. Combining Algorithms<\/h3>\n
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.<\/p>\n

9.4. Bit Manipulation<\/h3>\n
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.<\/p>\n

10. Practice Problems and Solutions<\/h2>\n
To reinforce your understanding of linked list cycle problems, here are some practice problems with their solutions:<\/p>\n