To find if a linked list has a loop

Problem: Suppose the last node in the linked list point back to any of the previous nodes, creating a loop. How will you detect this?


Use 2 pointers that traverses the list with different speed. For example, at each step, pointer1 will jump one node and pointer2 will jump 2 nodes.

Start both pointers from head.

ptr1=head.next;
ptr2=head.next.next;


Now that ptr2 has already marched ahead of ptr1, there's no chance these two pointers will point to the same node, unless there's a loop.