Find Loop in a Linked List

This case solves the problem of finding the starting node of a loop in a linked list.

A node in a linked list with a loop exists where the next pointer points to a previously visited node, creating a cycle. The task is to detect this loop and return the starting node of the loop if it exists.

For example, given a linked list like:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
            ^                            
            |_____________________________|

The node with value 3 is the starting node of the loop.

This problem involves using Floyd's Tortoise and Hare algorithm, also known as the cycle detection algorithm, which uses two pointers moving at different speeds to detect the presence of a loop. If a loop is found, the algorithm determines the starting node of the loop using additional pointer manipulations.

The solution I am providing below implements this algorithm to detect and return the starting node of the loop or None if no loop is present in the linked list.

Solution

My Approach Thought Process

The find_loop function takes the head node of a linked list as input and returns the starting node of a loop in the linked list, if it exists.

It uses Floyd's Tortoise and Hare algorithm to detect the loop in the linked list. Two pointers (first and second) are initialized to traverse the linked list at different speeds until they meet at a common node within the loop.

After detecting the loop, one pointer (first) is reset to the head of the linked list, and both pointers are moved one step at a time until they meet again at the starting node of the loop.

The function returns the loop's starting node or None if no loop is found.

The TestFindLoop class contains unit tests to verify the correctness of the findLoop function for various scenarios, including cases with no loop, loops starting from different nodes in the linked list, and loops starting from the first node.

Code Implementation

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

# O(n) time | O(1) space
def find_loop(head):
    """
    Find the starting node of a loop in a linked list, if it exists.

    Args:
        head (ListNode): The head node of the linked list.

    Returns:
        ListNode: The starting node of the loop. Returns None if no loop is found.
    """
    # Initialize two pointers: first and second
    first = head.next
    second = head.next.next
    
    # Move first and second pointers until they meet at a common node within the loop
    while first != second:
        if not second or not second.next:
            return None  # No loop found
        first = first.next
        second = second.next.next
    
    # Reset first pointer to the head and move both pointers one step at a time until they meet
    first = head
    while first != second:
        first = first.next
        second = second.next
    
    # Return the node where the pointers meet, which is the starting node of the loop
    return first

Time Complexity

The code's time complexity is O(n), with n being the number of nodes in the linked list. That is because the code iterates through the linked list once to detect the loop using Floyd's Tortoise and Hare algorithm.

Space Complexity

The code's space complexity is O(1) because it does not use extra space in the linked list's size. This constant space is used to store a few pointers (first and second) and temporary variables and does not depend on the size of the linked list.

Unit Test

import unittest
class TestFindLoop(unittest.TestCase):
    def test_no_loop(self):
        head = ListNode(1, ListNode(2, ListNode(3)))
        self.assertIsNone(find_loop(head))

    def test_loop_starting_from_second_node(self):
        head = ListNode(1)
        node2 = ListNode(2)
        head.next = node2
        node3 = ListNode(3)
        node2.next = node3
        node4 = ListNode(4)
        node3.next = node4
        node5 = ListNode(5)
        node4.next = node5
        node6 = ListNode(6)
        node5.next = node6
        node6.next = node2  # Create a loop
        self.assertEqual(find_loop(head), node2)

    def test_loop_starting_from_last_node(self):
        head = ListNode(1)
        node2 = ListNode(2)
        head.next = node2
        node3 = ListNode(3)
        node2.next = node3
        node4 = ListNode(4)
        node3.next = node4
        node5 = ListNode(5)
        node4.next = node5
        node6 = ListNode(6)
        node5.next = node6
        node6.next = node5  # Create a loop
        self.assertEqual(find_loop(head), node5)

    def test_loop_starting_from_first_node(self):
        head = ListNode(1)
        node2 = ListNode(2)
        head.next = node2
        node3 = ListNode(3)
        node2.next = node3
        node4 = ListNode(4)
        node3.next = node4
        node5 = ListNode(5)
        node4.next = node5
        node6 = ListNode(6)
        node5.next = node6
        node6.next = head  # Create a loop
        self.assertEqual(find_loop(head), head)

if __name__ == "__main__":
    unittest.main()