如何检测链表中的循环？-Java 学习之路

388

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

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

每个节点指向下一个节点，最后一个节点除外 . 假设列表有可能包含循环 - 即最终节点而不是具有空值，则引用列表中的一个节点，该节点位于它之前 .

什么是最好的写作方式

boolean hasLoop(Node first)

如果给定节点是带循环的列表中的第一个，则返回 true ，否则返回 false ？你怎么写，这需要一个恒定的空间和合理的时间？

这是一个循环列表的图片：

alt text

23 回答

Algorithm

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

Complexity

Time ~ O(n)
Space ~ O(n)

回复于 2024-04-27T12:50:22+08:00

这是我在java中的解决方案

boolean detectLoop(Node head){
    Node fastRunner = head;
    Node slowRunner = head;
    while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
        fastRunner = fastRunner.next.next;
        slowRunner = slowRunner.next;
        if(fastRunner == slowRunner){
            return true;
        }
    }
    return false;
}

回复于 2024-04-27T12:50:22+08:00

这是检测循环的解决方案 .

public boolean hasCycle(ListNode head) {
            ListNode slow =head;
            ListNode fast =head;

            while(fast!=null && fast.next!=null){
                slow = slow.next; // slow pointer only one hop
                fast = fast.next.next; // fast pointer two hops 

                if(slow == fast)    return true; // retrun true if fast meet slow pointer
            }

            return false; // return false if fast pointer stop at end 
        }

回复于 2024-04-27T12:50:22+08:00

-1

处理这个帖子我可能会非常迟到 . 但还是..

为什么不能将节点的地址和指向的“下一个”节点存储在表中

如果我们可以这样制表

node present: (present node addr) (next node address)

node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

因此形成了一个循环 .

回复于 2024-04-27T12:50:22+08:00

您可以使用Floyd's cycle-finding algorithm，也称为乌龟和野兔算法 .

我们的想法是对列表进行两次引用，然后在 different speeds 处移动它们 . 通过 1 节点向前移动一个节点，通过 2 节点向前移动另一个节点 .

如果链表有一个循环，它们肯定会遇到 .
否则两个引用中的任何一个（或它们的 next ）都将变为 null .

实现该算法的Java函数：

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list

    while(true) {

        slow = slow.next;          // 1 hop

        if(fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false;          // next node null => no loop

        if(slow == null || fast == null) // if either hits null..no loop
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop
            return true;
    }
}

回复于 2024-04-27T12:50:22+08:00

// To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
    Node slower, faster;
    slower = head;
    faster = head.next; // start faster one node ahead
    while (true) {

        // if the faster pointer encounters a NULL element
        if (faster == null || faster.next == null)
            return false;
        // if faster pointer ever equals slower or faster's next
        // pointer is ever equal to slower then it's a circular list
        else if (slower == faster || slower == faster.next)
            return true;
        else {
            // advance the pointers
            slower = slower.next;
            faster = faster.next.next;
        }
    }
}

回复于 2024-04-27T12:50:22+08:00

-2
Tortoise and hare

看看Pollard's rho algorithm . 它's not quite the same problem, but maybe you'将理解它的逻辑，并将其应用于链表 .

（如果你很懒，你可以查看cycle detection - 检查关于乌龟和野兔的部分 . ）

这只需要线性时间和2个额外指针 .

在Java中：
```
boolean hasLoop( Node first ) {
    if ( first == null ) return false;

    Node turtle = first;
    Node hare = first;

    while ( hare.next != null && hare.next.next != null ) {
         turtle = turtle.next;
         hare = hare.next.next;

         if ( turtle == hare ) return true;
    }

    return false;
}
```
（大多数解决方案都没有检查 next 和 next.next 是否为空 . 此外，由于乌龟总是落后，你不必检查它是否为空 - 野兔已经这样做了 . ）
回复于 2024-04-27T12:50:22+08:00

如果我们允许嵌入类 Node ，我会解决问题，因为我已经在下面实现了它 . hasLoop() 在O（n）时间内运行，并且仅占用 counter 的空间 . 这似乎是一个合适的解决方案吗？或者有没有办法在不嵌入 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;
        ....
    }

}

回复于 2024-04-27T12:50:22+08:00

用户unicornaddict上面有一个很好的算法，但遗憾的是它包含了奇数长度> = 3的非循环列表的错误 . 问题是 fast 可以在列表结尾之前得到"stuck"， slow 赶上它，并且（错误地）检测到循环 .

这是修正后的算法 .

static boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either.
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list.

    while(true) {
        slow = slow.next;          // 1 hop.
        if(fast.next == null)
            fast = null;
        else
            fast = fast.next.next; // 2 hops.

        if(fast == null) // if fast hits null..no loop.
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}

回复于 2024-04-27T12:50:22+08:00

47

检测链表中的循环可以以最简单的方式之一完成，这导致O（N）复杂度 .

当您从头开始遍历列表时，创建一个已排序的地址列表 . 插入新地址时，请检查已排序列表中的地址是否已存在，这会导致O（logN）复杂性 .

回复于 2024-04-27T12:50:22+08:00

对于Turtle和Rabbit的替代解决方案，并不像我暂时更改列表那样好：

我们的想法是走在列表中，并在您前进时将其反转 . 然后，当您第一次到达已经访问过的节点时，其下一个指针将指向"backwards"，导致迭代再次朝向 first 继续，在此处终止 .

Node prev = null;
Node cur = first;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}
boolean hasCycle = prev == first && first != null && first.next != null;

// reconstruct the list
cur = prev;
prev = null;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

return hasCycle;

测试代码：

static void assertSameOrder(Node[] nodes) {
    for (int i = 0; i < nodes.length - 1; i++) {
        assert nodes[i].next == nodes[i + 1];
    }
}

public static void main(String[] args) {
    Node[] nodes = new Node[100];
    for (int i = 0; i < nodes.length; i++) {
        nodes[i] = new Node();
    }
    for (int i = 0; i < nodes.length - 1; i++) {
        nodes[i].next = nodes[i + 1];
    }
    Node first = nodes[0];
    Node max = nodes[nodes.length - 1];

    max.next = null;
    assert !hasCycle(first);
    assertSameOrder(nodes);
    max.next = first;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = max;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = nodes[50];
    assert hasCycle(first);
    assertSameOrder(nodes);
}

回复于 2024-04-27T12:50:22+08:00

497

Better than Floyd's algorithm

理查德布伦特描述了alternative cycle detection algorithm，这非常像野兔和乌龟[Floyd 's cycle] except that, the slow node here doesn' t移动，但后来"teleported"以固定间隔到达快节点的位置 .

这里有描述：http://www.siafoo.net/algorithm/11布伦特声称他的算法比Floyd的循环算法快24％到36％ . O（n）时间复杂度，O（1）空间复杂度 .

public static boolean hasLoop(Node root){
    if(root == null) return false;

    Node slow = root, fast = root;
    int taken = 0, limit = 2;

    while (fast.next != null) {
        fast = fast.next;
        taken++;
        if(slow == fast) return true;

        if(taken == limit){
            taken = 0;
            limit <<= 1;    // equivalent to limit *= 2;
            slow = fast;    // teleporting the turtle (to the hare's position) 
        }
    }
    return false;
}

回复于 2024-04-27T12:50:22+08:00

这是我的可运行代码 .

我所做的是通过使用三个跟踪链接的临时节点（空间复杂度 O(1) ）来尊重链表 .

这样做的有趣事实是帮助检测链表中的循环，因为当你继续前进时，你不希望回到起点（根节点），其中一个临时节点应该变为null，除非你有一个循环，这意味着它指向根节点 .

该算法的时间复杂度为 O(n) ，空间复杂度为 O(1) .

这是链表的类节点：

public class LinkedNode{
    public LinkedNode next;
}

这是主代码，其中包含三个节点的简单测试用例，最后一个节点指向第二个节点：

public static boolean checkLoopInLinkedList(LinkedNode root){

        if (root == null || root.next == null) return false;

        LinkedNode current1 = root, current2 = root.next, current3 = root.next.next;
        root.next = null;
        current2.next = current1;

        while(current3 != null){
            if(current3 == root) return true;

            current1 = current2;
            current2 = current3;
            current3 = current3.next;

            current2.next = current1;
        }
        return false;
    }

以下是最后一个节点指向第二个节点的三个节点的简单测试用例：

public class questions{
    public static void main(String [] args){

        LinkedNode n1 = new LinkedNode();
        LinkedNode n2 = new LinkedNode();
        LinkedNode n3 = new LinkedNode();
        n1.next = n2;
        n2.next = n3;
        n3.next = n2;

        System.out.print(checkLoopInLinkedList(n1));
    }
}

回复于 2024-04-27T12:50:22+08:00

8

您也可以使用上面答案中建议的Floyd's tool算法 .

该算法可以检查单链表是否具有闭合循环 . 这可以通过迭代具有将以不同速度移动的两个指针的列表来实现 . 这样，如果有一个循环，则两个指针将在某个时刻相遇在将来 .

请随意查看链接列表数据结构中的blog post，其中我还包含一个代码片段，其中包含上述java语言算法的实现 .

问候，

安德烈亚斯（@xnorcode）

回复于 2024-04-27T12:50:22+08:00

public boolean isCircular() {

    if (head == null)
        return false;

    Node temp1 = head;
    Node temp2 = head;

    try {
        while (temp2.next != null) {

            temp2 = temp2.next.next.next;
            temp1 = temp1.next;

            if (temp1 == temp2 || temp1 == temp2.next) 
                return true;    

        }
    } catch (NullPointerException ex) {
        return false;

    }

    return false;

}

回复于 2024-04-27T12:50:22+08:00

28

我无法看到任何方法使这需要一定的时间或空间，两者都会随着列表的大小而增加 .

我会使用IdentityHashMap（假设还没有IdentityHashSet）并将每个Node存储到 Map 中 . 在存储节点之前，您将在其上调用containsKey . 如果节点已经存在，则您有一个循环 .

ItentityHashMap使用==而不是.equals，以便您检查对象在内存中的位置，而不是它具有相同的内容 .

回复于 2024-04-27T12:50:22+08:00
104

你甚至可以在持续的O（1）时间内完成它（虽然它不会非常快或有效）：计算机内存可以容纳的节点数量有限，比如N个记录 . 如果遍历超过N条记录，那么就有一个循环 .

回复于 2024-04-27T12:50:22+08:00

这种方法有空间开销，但实现更简单：

可以通过在Map中存储节点来识别循环 . 在放置节点之前;检查节点是否已存在 . 如果节点已存在于 Map 中，则表示链接列表具有循环 .

public boolean loopDetector(Node<E> first) {  
       Node<E> t = first;  
       Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();  
       while (t != null) {  
            if (map.containsKey(t)) {  
                 System.out.println(" duplicate Node is --" + t  
                           + " having value :" + t.data);  

                 return true;  
            } else {  
                 map.put(t, t);  
            }  
            t = t.next;  
       }  
       return false;  
  }

回复于 2024-04-27T12:50:22+08:00

这是快速/慢速解决方案的改进，可正确处理奇数长度列表并提高清晰度 .

boolean hasLoop(Node first) {
    Node slow = first;
    Node fast = first;

    while(fast != null && fast.next != null) {
        slow = slow.next;          // 1 hop
        fast = fast.next.next;     // 2 hops 

        if(slow == fast)  // fast caught up to slow, so there is a loop
            return true;
    }
    return false;  // fast reached null, so the list terminates
}

回复于 2024-04-27T12:50:22+08:00

0
这个代码经过优化，产生的结果比选择最佳答案的结果更快 . 这个代码可以避免进入一个非常长的追逐前向和后向节点指针的过程，如果我们遵循“最好的”，这将在下面的情况下发生回答'方法 . 看看下面的干运行，你会意识到我想说的话 . 然后通过下面给出的方法看问题，并测量一下 . 找到答案的步骤 .

1-> 2-> 9-> 3 ^ -------- ^

这是代码：
```
boolean loop(node *head)
{
 node *back=head;
 node *front=head;

 while(front && front->next)
 {
  front=front->next->next;
  if(back==front)
  return true;
  else
  back=back->next;
 }
return false
}
```
回复于 2024-04-27T12:50:22+08:00

以下可能不是最好的方法 - 它是O（n ^ 2） . 但是，它应该有助于完成工作（最终） .

count_of_elements_so_far = 0;
for (each element in linked list)
{
    search for current element in first <count_of_elements_so_far>
    if found, then you have a loop
    else,count_of_elements_so_far++;
}

回复于 2024-04-27T12:50:22+08:00

-1
```
public boolean hasLoop(Node start){   
   TreeSet<Node> set = new TreeSet<Node>();
   Node lookingAt = start;

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

       if (set.contains(lookingAt){
           return false;
        } else {
        set.put(lookingAt);
        }

        return true;
}   
// Inside our Node class:        
public Node peek(){
   return this.next;
}
```
请原谅我的无知（我还是Java和编程方面的新手），但为什么上述工作不起作用呢？

我想这并不能解决恒定的空间问题......但它确实至少在合理的时间到达那里，对吗？它只占用链表的空间加上具有n个元素的集合的空间（其中n是链表中的元素数，或者直到它到达循环的元素数） . 对于时间，我认为最坏情况分析会建议O（nlog（n）） . contains（）的SortedSet查找是log（n）（检查javadoc，但我很确定TreeSet的底层结构是TreeMap，它又是一个红黑树），在最坏的情况下（没有循环，或者在最后循环），它必须进行n次查找 .
回复于 2024-04-27T12:50:22+08:00

boolean hasCycle(Node head) {

    boolean dec = false;
    Node first = head;
    Node sec = head;
    while(first != null && sec != null)
    {
        first = first.next;
        sec = sec.next.next;
        if(first == sec )
        {
            dec = true;
            break;
        }

    }
        return dec;
}

使用上面的函数来检测java中的链表中的循环 .

回复于 2024-04-27T12:50:22+08:00

如何检测链表中的循环？

23 回答

相关问题