2.8 Loop Detection – CCI

  • In a circular linked list, if we advance one pointer at one node per turn and another pointer at two nodes per turn, they will eventually collide
  • If we say the point at which the slow node enters the loop is k nodes from the start, then the fast pointer will be k nodes into the loop at that point
  • One in the loop together, it will take the fast pointer (loop_size – k) turns to catch up to the slow pointer
  • This means the collision point is k distance away from the beginning of the loop.
  • loop-size – (loop_size – k) = k
  • The start of the list is also k distance away from the start of the loop
  • Traversing from the start of the list and the collision point will eventually lead us to the start of the loop
# [2.8] Loop Detection: Given a circular linked list, implement
# an algorithm that returns the node at the beginning of the
# loop.

# Space complexity: O(1)
# Time complexity: O(n)

import unittest

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


def get_start_loop_node(node):
    first = node
    slow = node
    fast = node

    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next

        if fast == slow:
            loop_start_node = find_intersection(slow, first)
            return loop_start_node

    return None

def find_intersection(node1, node2):
    while node1 != node2:
        node1 = node1.next
        node2 = node2.next

    return node1

class Test(unittest.TestCase):
    
    def test_get_start_loop_node(self):
        n1 = Node(1)
        n2 = Node(2)
        n3 = Node(3)
        n4 = Node(4)
        n5 = Node(5)
        n1.next = n2
        n2.next = n3
        n3.next = n4
        n4.next = n5
        self.assertEqual(get_start_loop_node(n1), None)
        
        n5.next = n3
        self.assertEqual(get_start_loop_node(n1), n3)
        
if __name__ == '__main__':
    unittest.main()