Q107: Linked list with a cycle

Posted on by bytesoftheday

Question #107: Following linked list is an example of linked list with a cycle.

linked_list_cycle

Which of the following is a method to detect if there is a loop in a linked list of unknown size?

Options:

  • Take two pointers, start traversing using the first pointer and start the second pointer after first pointer has reached second element of the linked list. If the pointers meet, there is a cycle/loop.
  • Take two pointers, increment first pointer by one step and second pointer by two steps. If the pointers meet, there is a cycle/loop.
  • Starting from the first element in the list, assume that it’s the part of the loop. Start traversal from that element till the element repeats. Repeat for all of the elements.
  • Both 1 and 2.

Solution: The correct answer is option 2. Option 1 will detect cycle of size 2 only. Option 3 will loop forever if the first element of the linked list is not part of the cycle.