java - Java中如何判断一个链表是否有环？

Question

我有以下实现来检查链表是否有循环。如果是，它将返回 true，如果不是，则返回 false。

看起来代码是正确的，但即使它确实有一个循环，它也返回 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 步， 如果列表有循环，最终会相遇， 否则到达列表的末尾。

此循环检测实现不是根据节点值检测循环，而是根据节点检测循环。 就节点而言，这里没有循环:

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;