8) Detect Loop in linked list

In this article, we going to see how to detect loop in a linked list.

Here is our given problem,

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

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.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
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: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

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

Explanations:

Using slow and fast pointer

  1. Slow pointer moves by one position.
  2. Fast pointer moves by two positions.

When fast pointer reaches null, it indicates that, there is no cycle or loop.

When fast pointer and slow pointer meets the same position (poiter), it indicates that, there is a cycle or loop in a linked list.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(slow != null && fast != null && fast.next != null)
        {    
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast)
            {
                return true;
            }
        }
        return false;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Diagrammatic Explanations:

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=”false” ]

0 thoughts on “8) Detect Loop in linked list”

  1. Pingback: 9) Linked List Cycle II – Developers Inspired

Leave a Comment

Your email address will not be published. Required fields are marked *