LeetCode 141. Linked List Cycle (solution with images)

Problem: →

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Solution: →

We can solve this problem using two pointer approach.

For this problem, let’s see what will happen if there’s a circle. If it’s a little difficult, then let’s think about we are running on a circular track.

If the track is 100m long, your speed is 10m/s, your friend’s speed is 5m/s.

Then after 20s, you’ve run 200m, your friend has run 100m. But because the track is circular, so you will be at the same place with your friend since the difference between your distances is exactly 100m.

Lets understand with code,

First, we are taking slow and fast variables, which are pointing to head of given linked list.

— — First Iteration — —

Now, we are going to enter in while loop, to move slow and fast,

Now, fast will move, two steps, while slow will move 1 step,

Now, in if condition, we will check both Nodes, if they are same or not.

Here it is not matching, so if condition will become false.

— — Second Iteration — —

Now, for the next iteration,

Now, fast will move, two steps, while slow will move 1 step,

Then in if condition, we will check both Nodes, if they are same or not.

Here it is not matching, so if condition will become false.

— — Third Iteration — —

Now, for the next iteration,

Now, fast will move, two steps, while slow will move 1 step,

Then in if condition, we will check both Nodes, if they are same or not.

Here it is not matching, so if condition will become false.

— — Forth Iteration — —

Now, for the next iteration,

Now, fast will move, two steps, while slow will move 1 step,

Then in if condition, we will check both Nodes, if they are same or not.

Here it is matching, so if condition will become true and it will return true.

Here, true is our answer.

Now, lets see full source code,

Code (Java): →

Code (Python): →

Time Complexity

Here, we are traversing a whole linkedlist so, total time complexity will be O(n).

Space Complexity

Here, We have used two variables only, so total space complexity will also be O(1).

— — — — — — — — — — — — — — — — — — — — — — — — —

—> Checkout below problem, which is same as above, with little bit more difficulty

Thanks for reading this article ❤

If this article helps you, please clap 👏 this article.

Please follow me on medium, I will post useful information like above.

Instagram → https://www.instagram.com/alexmurphyas8/

Twitter → https://twitter.com/AlexMurphyas8

If I got something wrong? Let me in the comments. I would love to improve.