Detect cycle in a linked list.

Problem:

A singly-linked data structure is a data structure made up of nodes where each node has a pointer to the next node (or a pointer to null). Suppose that you have a pointer to the first node of a singly-linked list data structure:

  • Determine whether a singly-linked data structure contains a cycle. You may use only two pointers into the list (and no other variables). The running time of your algorithm should be linear in the number of nodes in the data structure.
  • If a singly-linked data structure contains a cycle, determine the first node that participates in the cycle. you may use only a constant number of pointers into the list (and no other variables). The running time of your algorithm should be linear in the number of nodes in the data structure.

You may not modify the structure of the linked list.

Solution:

  1. maintain a tortoise pointer that advances one node per time step and a hare pointer that advances two nodes per time step.
  2. once hare meets tortoise, it means there is a loop.
  3. then one pointer freezes, the other one keeps moving one node per step and counts the length of the loop.
  4. then one pointer points to the head of the list, the other one moves nodes ahead. Then both of them advance one node per step, once they meet each other we find the beginning node of the loop.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s