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

fast, slow
, Initially all point to the head node. Fast pointer
fast
Move backward one bit at a time, slow pointer
slow
Move backward two bits at a time; if the fast and slow pointers meet (point to the same node and are not empty), it means that there is a ring in the linked list.

//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

entrance
, The node where the fast and slow pointers meet is
meet
, Since the speed of the fast pointer is twice that of the slow pointer, when the fast and slow pointers meet, the distance traveled by the slow pointer is
s
, The distance traveled by the fast pointer is
2s
.

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

he
, The distance from the ring entrance to the meeting node is
em
, The length of the loop is
r
.

We can get:

$s = he + em/2s = he + em + n*r$

among them,

n
Indicates the number of turns of the ring that the fast hand travels. and so$s = n*r$ , that is, the distance traveled by the slow pointer is an integer multiple of the ring length when they meet.

Suppose the length of the linked list is

L
,Have
L = he + r
,then

$s = he + em = n*r = (n-1)*r + r = (n-1)*r + L-he$

get

$he = (n-1)*r = L-he-em = (n-1)*r + r-em$

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
with
meet
• 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
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