Given a linked list, determine if it has a cycle in it [duplicate]

Question

This question already has answers here:

How to detect a loop in a linked list? (29 answers)

Closed 10 years ago.

I am looking at the following code from programcreek.com on finding cycles in linked list and wondering how variable 'head' of type ListNode is declared here by passing it as an argument to the boolean method. Is there a data type ListNode in Java. I can't seem to find it in the documentation. Secondly, how do we analyze time and space complexity for this.

public class Solution {
 public boolean hasCycle(ListNode head) {
 ListNode fast = head;
 ListNode slow = head;
 if(head == null)
 return false;
 if(head.next == null)
 return false;
 while(fast != null && fast.next != null){
 slow = slow.next;
 fast = fast.next.next;
 if(slow == fast)
 return true;
 }
 return false;
 }
}

• Srinath Ganesh: stackoverflow.com/a/2663147/1897935 two people run around a circle at different speeds . both have to met at some point of time . (IF it has 2 directions then u can go from both way and find cycle BUT u just have one direction )

Answer 1

In this function boolean is the return type of the funtion hasCycle(). The input of this function is object of Class ListNode for which you need to find cycle if exists. This function works fine. I don't think Java has a class named ListNode. You can find the time complexity here

• Sam Lot: Since input of this function is object of Class ListNode should the class ListNode be declared separately for the code to work ?

Answer 2

ListNode classis not defined in java and it has to be defined separately.Here is an example of how it can be defined

public class linkedlistcycle {
 class ListNode {
 int val;
 ListNode next;
 ListNode(int x) {
 val = x;
 next = null;
 }
 }
 public boolean hasCycle(ListNode head){
 ListNode a = head ;
 ListNode b = head ;
 if ((head == null) || (head.next==null))
 { return false;}
 while ((head != null) | (head.next != null))
 {
 a = a.next ;
 b = b.next.next;
 if(a == b)
 return true;
 } 
 return false ;
 }
 }