假设您在Java中有一个链表结构。它由节点组成:

class Node {
    Node next;
    // some user data
}

每个节点都指向下一个节点,除了最后一个节点,它的next为空。假设有一种可能性,列表可以包含一个循环-即最后的节点,而不是有一个空值,有一个引用到列表中它之前的一个节点。

最好的写作方式是什么

boolean hasLoop(Node first)

如果给定的节点是带有循环的列表的第一个,则返回true,否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?

下面是一个带有循环的列表的图片:


当前回答

您甚至可以在常数O(1)时间内完成(尽管它不是非常快或有效):计算机内存可以容纳的节点数量是有限的,比如N条记录。如果遍历超过N条记录,那么就有一个循环。

其他回答

算法

public static boolean hasCycle (LinkedList<Node> list)
{
    HashSet<Node> visited = new HashSet<Node>();

    for (Node n : list)
    {
        visited.add(n);

        if (visited.contains(n.next))
        {
            return true;
        }
    }

    return false;
}

复杂性

Time ~ O(n)
Space ~ O(n)
func checkLoop(_ head: LinkedList) -> Bool {
    var curr = head
    var prev = head
    
    while curr.next != nil, curr.next!.next != nil {
        curr = (curr.next?.next)!
        prev = prev.next!
        
        if curr === prev {
            return true
        }
    }
    
    return false
}

在这个上下文中,到处都有文本材料的加载。我只是想张贴一个图表表示,真正帮助我掌握概念。

当快、慢在点p相遇时,

快速行进的距离= a+b+c+b = a+2b+c

慢行距离= a+b

因为快的比慢的快2倍。 所以a+2b+c = 2(a+b)然后得到a=c。

因此,当另一个慢指针再次从头部运行到q时,同时,快速指针将从p运行到q,因此它们在q点会合。

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next==null)
        return null;

    ListNode slow = head;
    ListNode fast = head;

    while (fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;

        /*
        if the 2 pointers meet, then the 
        dist from the meeting pt to start of loop 
        equals
        dist from head to start of loop
        */
        if (fast == slow){ //loop found
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }            
    }
    return null;
}

如果允许我们嵌入类Node,我将像下面实现的那样解决这个问题。hasLoop()在O(n)时间内运行,并且只占用计数器的空间。这是不是一个合适的解决方案?或者是否有一种不嵌入Node的方法?(显然,在真正的实现中会有更多的方法,如RemoveNode(Node n)等。)

public class LinkedNodeList {
    Node first;
    Int count;

    LinkedNodeList(){
        first = null;
        count = 0;
    }

    LinkedNodeList(Node n){
        if (n.next != null){
            throw new error("must start with single node!");
        } else {
            first = n;
            count = 1;
        }
    }

    public void addNode(Node n){
        Node lookingAt = first;

        while(lookingAt.next != null){
            lookingAt = lookingAt.next;
        }

        lookingAt.next = n;
        count++;
    }

    public boolean hasLoop(){

        int counter = 0;
        Node lookingAt = first;

        while(lookingAt.next != null){
            counter++;
            if (count < counter){
                return false;
            } else {
               lookingAt = lookingAt.next;
            }
        }

        return true;

    }



    private class Node{
        Node next;
        ....
    }

}

我看不出有任何方法可以让这花费固定的时间或空间,两者都会随着列表的大小而增加。

我将使用IdentityHashMap(假设还没有IdentityHashSet)并将每个节点存储到映射中。在存储节点之前,您可以对其调用containsKey。如果节点已经存在,则有一个周期。

ItentityHashMap使用==而不是.equals,这样你就可以检查对象在内存中的位置,而不是它是否具有相同的内容。