- 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()