如何检查一个链表在Java中是否有环？

Question

我有以下实现来检查链表是否有循环。如果是，则 return 为真，否则为假。

看起来代码是正确的，但它 returning false 即使它确实有一个循环。我错过了什么？谢谢

import java.util.*;

class ListNode {
     int val;
     ListNode next;

     ListNode(int x) {
        val = x;
        next = null;
     }
 }

class LinkedListCycle {
    boolean hasCycle(ListNode head) {
        if(head == null) {
            return false;
        }

        ListNode walker = head;
        ListNode runner = head;

        while(runner.next!=null && runner.next.next!=null) {
            walker = walker.next;
            runner = runner.next.next;
            if(walker==runner) return true;
        }

        return false;
    }

    public static void main(String args[]) {
        LinkedListCycle llc = new LinkedListCycle();

        ListNode ln = new ListNode(1);
        ln.next = new ListNode(2);
        ln.next.next = new ListNode(3);
        ln.next.next.next = new ListNode(4);
        ln.next.next.next.next = new ListNode(2);
        ln.next.next.next.next.next = new ListNode(1);

        System.out.println(llc.hasCycle(ln));
    }
 }

Answer 1

算法确实正确： walker前进一步，runner前进2步，如果列表有循环，最终会相遇，否则到达列表末尾。

此循环检测实现不根据 节点值 检测循环，而是根据节点检测循环。 nodes:

这里没有循环

ListNode ln = new ListNode(1);
ln.next = new ListNode(2);
ln.next.next = new ListNode(3);
ln.next.next.next = new ListNode(4);
ln.next.next.next.next = new ListNode(2);
ln.next.next.next.next.next = new ListNode(1);

如果这样写就会有：

ListNode ln = new ListNode(1);
ln.next = new ListNode(2);
ln.next.next = new ListNode(3);
ln.next.next.next = new ListNode(4);
ln.next.next.next.next = ln.next;

如何检查一个链表在Java中是否有环？

How to check if a linked list has a cycle in Java?

java

algorithm

linked-list

cycle