141 Linked List Cycle · LeetCode Solutions solve Now

Problem

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

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. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

circularlinkedlist

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

Example 2:

circularlinkedlist test2

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

Example 3:

circularlinkedlist test3

Input: head = [1], pos = -1 Output: false 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?

Process to solve Linked List cycle problem

  • To solve Linked List cycle problem?, first, check if the given head of a linked list and head.next is null or not. If they are null return false.
  • Define two new variables slow and fast, both will store head of given linkedList.
  • Go through fast variable in a while loop until its value is null and fast.next value is null.
  • Jump one pointer of slow and for fast jump two.
  • Check if slow and fast objects are same.
  • If we are somehow out of the while loop, because our fast and fast.next is null. We can return false.

Solution

public class Solution {
    public bool HasCycle(ListNode head) {
        
        if (head == null || head.next == null) {
            return false;
        }
        
        var slow = head;
        var fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
}

Leave a Reply

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