Loop List is very common in interview. This article we give a more strict short statement about its solving.
One method to check if there's a loop in a list is to use two speed pointers. But most of articles did not give a proof.
Assume we have a list:
ListNode* head;
Then, we set two pointers start from the head, and one pointer added by 1 step, the other added by 2 steps:
ListNode* p1 = head, *p2 = head;
...
p1 = (p1 -> next) -> next;
p2 = p2 -> next;
Now, we need to proof that, if there's a loop in the list, p1 will meet p2.
- p1 obviously will exceed p2.
- As p1 can only added two steps every time, there're only two relative positions between p1 and p2.
- p1 just before p2. Then as p1 updates first, p2 updates second, they'll meet.
- There's a node between p1 and p2. As p1 updates first, they'll meet.