In this article we going to see about how to Detect Loop in a Linked List and Return the Loop Node.

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 = 1Output:tail connects to node index 1Explanation:There is a cycle in the linked list, where tail connects to the second node.

**Example 2:**

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

**Example 3:**

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

## 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:

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode temp = head; ListNode p = findWhereNodesMeeting(temp); if(p != null) { ListNode q = head; while(p != q) { p = p.next; q = q.next; } return p; } return null; } public ListNode findWhereNodesMeeting(ListNode head) { ListNode p = head; ListNode q = head; 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😊