给定一个链表，判断其中是否有环

Question

我正在查看 programcreek.com 中关于在链表中查找循环的以下代码，并想知道如何通过将变量 'head' 作为参数传递给布尔方法来声明类型为 ListNode 的变量。 Java中是否有数据类型ListNode。我似乎无法在文档中找到它。其次，我们如何分析时间和space复杂度。

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

Answer 1

在这个函数中 boolean 是函数 hasCycle() 的 return 类型。此函数的输入是 Class ListNode 的对象，如果存在，则需要为其查找循环。这个功能工作正常。我认为 Java 没有一个名为 ListNode 的 class。可以求时间复杂度here

Answer 2

ListNode 类未在 java 中定义，必须定义 separately.Here 是如何定义它的示例

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

java

algorithm

linked-list