# 9) Linked List Cycle II

Below is our given problem from Leetcode,

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

To represent a cycle in the given linked list, we use an integer `pos` which represents the position (0-indexed) in the linked list where tail connects to. If `pos` is `-1`, then there is no cycle in the linked list.

Note: 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 = , pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
```

Follow-up:
Can you solve it without using extra space?

### Basic Knowledge:

Before proceeding you must have good knowledge of detecting loop in a linked list. For that, I made an with detailed explanations.

1. How to detect cycle in linked list

## Explanation:

Once you find the cycle, return the node which meeting each other.

Make one pointer from head(Let’s say q) and another pointer(Let’s say p from node(which met each other).

Move p from one node to another node. Similarly move q from one node to another node, still both meets each other.

Repeat this process, until the node meets each other.

When both pointer meets at some point, it the starting node of cycle😜

## Solution:

```/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
ListNode p = findWhereNodesMeeting(temp);
if(p != null)
{
while(p != q)
{
p = p.next;
q = q.next;
}
return p;
}
return null;
}
{
while(p != null && q != null && q.next != null)
{
p = p.next;
q = q.next.next;
if(p == q)
{
return p;
}
}
return null;
}
}```

Time Complexity: O(n)

Space Complexity: O(1)

Note:

If you like this article, please subscribe my blog by entering your email id. So that, you won’t miss any new posts from me. I made a progress to solve algorithm problems daily with detailed and diagrammatic explanations, so others can easily understand the solution. Still now, I solved daily and made blogs with detailed explanations. If you like to support my work, please subscribe my blog via email. Kindly ignore, if you already subscribed😊

[jetpack_subscription_form show_only_email_and_button=”true” custom_background_button_color=”undefined” custom_text_button_color=”undefined” submit_button_text=”Subscribe” submit_button_classes=”undefined” show_subscribers_total=”true” ]