how this code works to find loop in linked list? [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

Best algorithm to test if a linked list has a cycle

p=head;

q=head->next;
while(p!=NULL && q!=NULL)

{

if(p==q) { //Loop detec开发者_JAVA百科ted! exit(0); }

p=p->next;

q=(q->next)?(q->next->next):q->next; --how this line works ??

}

---

First of all, if there is no loop in the list, the condition p==q will never be true, as q is always "ahead" of p.

Then, the distance between p and q is increased by one at each iteration. So if there's a loop, the condition p==q will be true as soon as the distance is a whole multiple of the loop length.

The line in question moves q ahead by 2 positions. It first checks if q would not reach the list end after moving forward by just one position in order to avoid null pointer dereferencing. (q->next is one position ahead of q, q->next->next is two positions ahead.)

---

Quote:

q=(q->next)?(q->next->next):q->next; --how this line works ??

This could also read:

if(q->next) {
  q = q->next->next;
} else {
  q = q->next;
}

---

This line of the code:

q=(q->next)?(q->next->next):q->next;

may be changed to this:

q=(q->next)?(q->next->next):NULL;

So it's simply a check if the list ended. If it is - than there isn't loop in it.

---

If you have a loop in a linked list, you can find it by running two pointers through the list, one advancing by one element through the list, the other by two elements.

If there's no loop, the "faster" one will always be ahead of the slower. If there's a loop, they will eventually point to the same element as they pass through the loop at different speeds.

All that the line

q=(q->next)?(q->next->next):q->next;

does is advance the faster pointer by two, if it can. If it can't because it's near the end of this list, it just advances by one.

In English, if this element is not the last, set the new pointer to the one beyond the next (which may be NULL). If this element is the last, set it to the next, which will be NULL.

Myself, I would have written it as:

q=(q->next)?(q->next->next):NULL;

but that's just a matter of style.

---

p always moves forward one step in the list on each iteration, but q moves two steps forward (unless the list ends; hence the check for the existence of q->next). This means that on every iteration q gets farther ahead of p. If there is no loop in the list, q will simply reach the end of the list and the loop will terminate. If there is a loop, then q will eventually loop over it (by going forwards faster) and “catch up” to p, i.e. p == q will be true.

(If you were additionally asking about the meaning of the specific line indicate, then it's just a shorter way of saying:

if (q-next) {
   q = q->next->next; // Go forward two steps if possible
} else {
   q = q->next; // Go forward one step otherwise
}

)