Deteting Circular Linked List

Q

Can you tell me how to check whether a linked list is circular?

✍: Guest

A

Create two pointers, and set both to the start of the list. Update each as follows:

while (pointer1) {
  pointer1 = pointer1->next;
  pointer2 = pointer2->next;
  if (pointer2) pointer2=pointer2->next;
  if (pointer1 == pointer2) {
    print ("circularn");
  }
}

If a list is circular, at some point pointer2 will wrap around and be either at the item just before pointer1, or the item before that. Either way, it's either 1 or 2 jumps until they meet.

2007-02-26, 6619👍, 0💬