Detailed explanation of Java's method to realize whether there is a cycle in a singly linked list

Author：Eve Cole Update Time：2024-11-24 09:24:02

This is a classic Microsoft written test question. The two pointers h1 and h2 traverse the singly linked list from the beginning. h1 moves forward 1 step each time, and h2 moves forward 2 steps each time. If h2 encounters NULL, it means that the ring does not exist. ; If h2 touches h1 that should be behind it, it means that a loop exists (that is, a loop occurs).

If the ring does not exist, h2 must encounter NULL first:

If the ring exists, h2 and h1 will definitely meet, and the meeting point is within the ring: h2 traverses faster than h1, and will definitely not meet at the beginning of the non-ring linked list, so when h1 and h2 both enter the ring Finally, each movement of h2 will reduce the gap between h2 and h1 in the forward direction by 1. Finally, the gap between h1 and h2 will be reduced to 0, that is, they meet.

Copy the code code as follows:

package org.myorg;
public class Test{
public static boolean isExsitLoop(SingleList a) {
Node<T> slow = a.head;
Node<T> fast = a.head; while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
return true;
}
return false;
}

public static void main(String args[]){
SingleList list = new SingleList();
for(int i=0;i<100;i++){
list.add(i);
}
System.out.print(SingleList.isExistingLoop(list));
}
}

Copy the code code as follows:

package org.myorg;
public class Node{
public Object data; //Data object stored in node
public Node next; //Reference pointing to the next node

public Node(Object value){
this.data = value;
}

publicNode(){
this.data = null;
this.next = null;
}

}

Copy the code code as follows:

package org.myorg;
public class SingleList{
private int size;
private Node head;

private void init(){
this.size = 0;
this.head = new Node();
}

public SingleList(){
init();
}

public boolean contains(Object value){
boolean flag = false;
Node p = head.next;
while(p!=null){
if(value.equals(p.data)){
flag = true;
break;
}else(
p = p.next;
)
}
return flag;
}

public boolean add(Object value){
if(contains(value))
return false;
else{
Node p = new Node(value);
p.next=head.next;
head.next = p;
size++;
}
return true;
}

}