Detect a loop in cyclic/circular linked list
- If a linked list has a cycle then no node has a
nullas next pointer.
- A simple loop exists when
p1.next.next !== nullas shown below.
- While iterating over the linked list we need two pointers,
p1increments one node at a time and the
p2increments two points at a time. If both the pointers meet then the loop exists.
If there is no loop then
p2can not meet as
p2is in the future, we have not invented time travel yet 🙂