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

Question

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;
    }
}

http://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 ) — Srinath Ganesh, Apr 13 '15 at 02:46

score 0 · Answer 1 · edited May 23 '17 at 12:07

0

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

edited May 23 '17 at 12:07

Community

1
1

answered Apr 13 '15 at 02:40

Nikhil Mahesh

56
6

Since input of this function is object of Class ListNode should the class ListNode be declared separately for the code to work ? – Sam Lot Apr 13 '15 at 12:13

score 0 · Accepted Answer · answered Apr 13 '15 at 12:51

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 ;

        }



    }

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

2 Answers2