判断单向链表有循环的算法（只给最佳答案50分）

Question

有一个单向链表：
class Node{
  Node next;
}如何判断此链表存在循环，例如 n0->n1->n2…->ni->….->nk->ni

Answer 1

实际代码是//IMPORTANT!这里。
class Node
{
Node next;
int value;
}public class Main {

public static void printLinkedList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.value);
current = current.next;
System.out.print(" ");
}
} //IMPORTANT!
public static boolean circleLinkedList(Node head) {

Node s1 = head.next;
Node s2 = (head.next != null) ? head.next.next : null;

while (s1 != s2) {
if (s1 == null || s1.next == null || s2 == null || s2.next == null)
return false; //Has the tail

s1 = s1.next;
s2 = s2.next.next;
}

return true;
}

public static void main(String[] args) { Node head = null;
Node current = null;
Node n5 = null;
for (int i = 0; i < 10; i++)
{
Node n = new Node();
if (head != null) {
n.value = i;
current.next = n;
current = n;
} else {
head = n;
current = n;
current.next = null;
current.value = i;
}

if (i == 5) {
n5 = current;
}
}

printLinkedList(head);

current.next = n5;

System.out.println(circleLinkedList(head)); }
}

Answer 2

其他大部分代码是用于创建链表，以及制造有环链表[current.next = n5;]这一句就是产生环的。可以注释或者不注释上，来试验结果。

Answer 3

遍历元素，一个个存到Set中，同时判断存入的元素是否已经存在，若存在则有循环

Answer 4

package com.future.pang;public class Node {// 指向下一节点
private Node next =  null;
// 存储数据
private Object obj = null;// 判断节点是不是最后一个
public boolean hasNext()
{
return next==null?false:true;
}

// 下一个节点
public Node next()
{
return this.getNext();
}

// 添加数据
public void add(Object obj)
{
this.obj  = obj;
}


// 设置节点
public void setNext(Node node)
{
this.next = node;
}
// 获得节点，同next（）方法一样
public Node getNext()
{
return this.next;
}
}

Answer 5

思路很简单，你这样想，有一条环状跑道，两个人在上面跑步，一个人快，一个人慢，那么两个人迟早是要相会的。有环链表也一样，你看成是跑道，我现在有s1和s2两个人，一个一次一步，一个一次两步。
不出一圈，两个准遇上，如果有环，没环的话，快的那个的next迟早是null~

Answer 6

class Node
{
    Node next;
    int value;
}
//唯一值
key=Random();
int node.value=key;
while(node.next!=null){
 if(node.next.value=key){
     return true;
 }}

Answer 7

class Node
{
    Node next;
    int value;
}public class Main {
    
    public static boolean isCircle(Node head) {
        
        Node s1 = head.next;
        while(s1 != null){
            if(s1 == head){
                 return true;
            }
            s1 = s1.next;
        }
        return false;
    }
}

Answer 8

我有一种方法，但是只能保证单线程，即不能有两个线程同时访问链表去判断是否有环
class Node{
Node next;
boolean get=false;//标识是否已经被遍历
}
public static void main(String[] args){
Node head=...;//打头
while(head!=null){
if(head.get){
System.out.println("存在环");
return;
}
else{
head.get=true;
head=head.next;
}
}
System.out.println("不存在环");
}
这种方法也可以应用于判断分支结构中是否有环。例如在java虚拟机垃圾回收过程中判断一个对象是否已经被遍历过，从而避免因对象之间引用关系构成环而造成的死循环

Answer 9

lz 说的是单向链表  。、 汗判断此链表存在循环？？？？ 我没明白lz说的是什么意思？
判断这个链表是否正在被读？ 还是这个链表不为空？？？？

Answer 10

healer_kx的方案比较cool。ps:显然还有人没理解题目。

Answer 11

呵呵，Thanks~楼主懂就足够了~