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.
- maintain a tortoise pointer that advances one node per time step and a hare pointer that advances two nodes per time step.
- once hare meets tortoise, it means there is a loop.
- then one pointer freezes, the other one keeps moving one node per step and counts the length l of the loop.
- then one pointer points to the head of the list, the other one moves l nodes ahead. Then both of them advance one node per step, once they meet each other we find the beginning node of the loop.