LeetCode 142. Linked List Cycle II (solution with images)

Problem: →

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:

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

Example 2:

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

Example 3:

Input: head = [1], pos = -1
Output: no cycle
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: →

Before moving further, I just recommended you to understand below solution first,

We can solve this problem using two pointer approach.

Below image is to understand it in general way,

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,

Here, it will iterate till, slow and fast will not become same,

— — Second Iteration — —

— — Third Iteration — —

— — Forth Iteration — —

Here, slow and fast will become same, so we will go inside inner while loop,

Here, if condition will become true,

Here you can see that, slow pointer to crossing node is L1+L2.

Fast pointer to crossing node is 2(L1+L2) since fast pointer always move 2 times of slow pointer step.

When slow and fast meet,

Distance traveled by fast pointer = 2 * (Distance traveled by slow pointer)

(m + n*x + k) = 2*(m + n*y + k)

x -->  Number of complete cyclic rounds made by 
       fast pointer before they meet first time

y -->  Number of complete cyclic rounds made by 
       slow pointer before they meet first time

Now,

(m + n*x + k) = 2*(m + n*y + k)

--> m + nx + k = 2m + 2ny + 2k

--> m + k = 2m + 2ny + 2k - nx

--> 2m - m + 2k - k + 2ny - nx = 0

--> m + k + n(2y -x) = 0

--> m + k = n(x - 2y)

Which means m+k is a multiple of n.

So if we start moving both pointers again at the same speed such that one pointer (say slow1) begins from the head node of the linked list and other pointers (say fast) begins from the meeting point.

When the slow1 pointer reaches the beginning of the loop (has made m steps), the fast would have made also moved m steps as they are now moving the same pace.

Finally, they meet at start of the circle,

Lets again go understand with code,

Now, we are talking another variable which is Slow1, which points to Head,

In inner while loop, we will iterate till, both slow1 and slow not become same,

— — Inner while loop Iteration 1 — -

— — Inner while loop Iteration 2— -

Here, slow == slow1,

So, inner while loop is terminated, and slow will be returned, which will be our answer.

Finally, slow is our answer.

Now, lets see full source code,

Code (Java): →

Code (Python): →

Time Complexity

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

Space Complexity

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

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.