9) Linked List Cycle II

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 = 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.

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:

/**
 * 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😊

Join 70 other followers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s