141. Linked List Cycle

Today, I did the question: Linked List Cycle.

Description:

https://leetcode.com/problems/linked-list-cycle/description/

We should check whether cycle exist or not. head and pos is given.

We can check the pos that which position is cycled back on the list. 

In example 1, 1st node is the returning node on the list.

 

Then, how do we check the cycle on the list?

 

The solution is similar to previous linked list question:

We are gonna make the slow and fast pointer again. 

As like the previous quesitons, the slow move only one node, and the fast moves two nodes on the list.

We can imagine the scenario that the slow pointer and fast pointer meet each other at some point!

 

From start point to the point that meet each other, we said the cycle!

 

Since the slow pointer move one node and fast pointer moves two nodes, the intervals between them is the integer incremented by 1 consistly. The two pointers are on the same cycle. On the cycle, they should meet each other if the interval integers increment. 

Solution:

If the slow pointer and fast pointer meet each other, we return True for this question. 

The while loop is looping until the fast pointer and fast.next pointer is NULL.

 

Time complexity: O(N) 

Space complexity: O(1)