2021/04/22

preface

The following list is a linked list with a ring. The entry of the ring is 2 and the length of the ring is 4.

List nodes are defined as follows:

// Single list node definition, refer to Leetcode
class ListNode<T> {
    public T val;
    public ListNode<T> next;

    public ListNode(a){
        this(null.null);
    }

    public ListNode(T val){
        this(val,null);
    }

    public ListNode(T val, ListNode next){
        this.val = val;
        this.next = next; }}Copy the code

Check whether the list has rings

The fast and slow pointer method is a better method to judge whether a linked list has a ring.

Define two Pointers, fast and slow, both pointing initially to the head node. The fast pointer moves backwards one bit at a time, and the slow pointer moves backwards two bits at a time; If the fast and slow Pointers meet (pointing to the same node and neither is null), the linked list has a ring.

// Check whether the list has rings
public boolean isLoop(a){
    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 the code

Defining ring inlet

If a linked list has rings, how do you determine which node is the entry to the ring (the node where the ring meets)?

Assume that the entrance of the linked list ring is the entrance, and the node where fast and slow Pointers meet is meet. Since the speed of the fast pointer is twice that of the slow pointer, when fast and slow Pointers meet, the distance traveled by the slow pointer is S, and the distance traveled by the fast pointer is 2s.

Assume that the distance from the head node to the ring entrance is HE, the distance from the ring entrance to the encounter node is em, and the length of the ring is R.

We can get:

Where, n represents the winding number of loops traversed by the fast pointer. So S =n∗rs = N *rs=n∗r, that is, when they meet, the distance covered by the slow Pointers is an integer multiple of the ring length.

If the length of the list is L, L = he + r, then

get

That is, if you move backwards from the encounter point and the head node at the same speed, and go through n-1 rings, you can meet at the ring entrance.

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

• Find the node where the fast and slow Pointers meetmeet
• Define two Pointers, one tohead 和 meet
• The double Pointers move backwards at the same time until both Pointers point to the same node, which is the entrance to the ring

 public ListNode getLoopEntrance(a){
    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
    if(meet == null) {return null;
    }
    // The fast and slow Pointers move backwards at the same speed from the point of encounter
    fast = head;
    slow = meet;
    while(fast ! = slow){ fast = fast.next; slow = slow.next; }return fast;
}
Copy the code

Determine the length of the ring

On a ring, the speed difference between the fast and slow hands is twice as great. Starting from the meeting node, the fast and slow Pointers move backward at their respective speeds in turn. The length of the slow pointer increases by 1 when the fast and slow Pointers move once. When the fast and slow Pointers meet, the distance covered by the slow pointer is the length of the ring.

public int getLoopLength(a) {
    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 point fast and slow meet for the first time}}// If the list has no loops, return 0
    if(! isLoop){return 0;
    }
    // Len starts with 1, and the fast and slow Pointers continue to move backwards
    int len = 1;
    slow = slow.next;
    fast = fast.next.next;
    while(slow ! = fast) { slow = slow.next; fast = fast.next.next; len++; }return len;
}
Copy the code