2021/04/22

# Preface

The following linked list is a linked list with loops, the entry of the loop is 2, and the length of the loop is 4.

The linked list nodes are defined as follows:

```
//Singly linked list node definition, refer to Leetcode
class ListNode < T > {
public T val;
public ListNode<T> next;
public ListNode () {
this ( null , null );
}
public ListNode (T val) {
this (val, null );
}
public ListNode (T val, ListNode next) {
this .val = val;
this .next = next;
}
}
Copy code
```

# Determine whether the linked list has a ring

Determining whether there is a ring list, a better approach is **speed pointer method** .

Define two pointers

```
//Determine whether the linked list has a loop
public boolean isLoop () {
if ( this .head == null ){
return false ;
}
ListNode<T> fast = head;
ListNode<T> slow = head;
while (fast != null && fast.next != null ) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
return true ;
}
}
return false ;
}
Copy code
```

# Determine the ring entrance

If there are rings in the linked list, how to determine which node is the entrance of the ring (the node where the rings meet)?

Suppose the entry of the linked list ring is

Suppose the distance from the head node to the ring entrance is

We can get:

among them,

Suppose the length of the linked list is

get

I.e. **, if the meeting point is moved backward from the head node and at the same speed, go through**

**n-1**

**A ring that can meet at the entrance of the ring**.

So we get the method of how to get the ring entry:

- Find the node where the fast and slow pointers meet meet
- Define two pointers, pointing to headwithmeet
- The two pointers move backward at the same time until the two pointers point to the same node, which is the entrance to the ring

```
public ListNode getLoopEntrance () {
if ( this .head == null ){
return null ;
}
ListNode<T> meet = null ;
ListNode<T> fast = head;
ListNode<T> slow = head;
while (fast != null && fast.next != null ) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
meet = fast;
break ;
}
}
//meet == null means there is no ring in the linked list
if there is no meeting if (meet == null ){
return null ;
}
//The fast and slow pointer moves backwards at the same speed from the point of meeting
fast = head;
slow = meet;
while (fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
Copy code
```

# Determine the length of the loop

On a ring, the difference between the fast and slow pointer speeds is twice. Starting from the meeting node, the fast and slow pointers move backwards at their respective speeds in turn, and the length of the slow pointer increases by 1 when the fast and slow pointers meet. The distance traveled by the slow pointer is the length of the loop when the fast and slow pointers meet.

```
public int getLoopLength () {
if (head == null || head.next == null ) {
return - 1 ;
}
ListNode<T> fast = head.next;
ListNode<T> slow = head.next;
boolean isLoop = false ;
while (fast != null && fast.next != null ) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
isLoop = true ;
break ; //At this time fast and slow meet for the first time
}
}
//If the linked list has no loops, return 0
if (!isLoop){
return 0 ;
}
//Has already met, len is initially 1, and the speed pointer continues to move backward
int len = 1 ;
slow = slow.next;
fast = fast.next.next;
while (slow != fast) {
slow = slow.next;
fast = fast.next.next;
len++;
}
return len;
}
Copy code
```