Make writing a habit together! This is the 15th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Topic describes

Give you the head node of a linked list and check if there are rings in the list.

If there is a node in the list that can be reached again by following the next pointer continuously, then there is a ring in the list. To represent the rings in a given list, the metric system internally uses the integer POS to represent where the tail of the list is connected to in the list (the index starts at 0). Note: pos is not passed as an argument. Just to identify the reality of linked lists.

Returns true if there are rings in the list. Otherwise, return false.

The sample

Input: head = [3,2,0,-4], pos = 1 output: true explanation: there is a ring in the linked list whose tail is connected to a second node.Copy the code

Input: head = [1,2], pos = 0 output: true explanation: there is a ring in the linked list whose tail is connected to the first node.Copy the code

Input: head = [1], pos = -1 Output: false Explanation: There are no loops in the linked list.Copy the code

prompt

  • The number of nodes in the linked list ranges from [0.10
    4 ^ 4     】
  • - 10
    5 ^ 5     < =Node.val< =10
    5 ^ 5
  • pos 为 - 1Or one of the linked listsEffective index 。

Double pointer

To determine whether a linked list has a ring, we can define a fast or slow pointer, and by moving the pointer, we can find the node that forms the ring.

Steps:

  1. Border judgment
  2. Define a fast pointer that moves two slots at a time and a slow pointer that moves one at a time
  3. Loop until the fast pointer is empty or the node that formed the ring is found
  4. Returns the result

public class Solution {
    public boolean hasCycle(ListNode head) {
        // boundary judgment
        if(head == null || head.next == null) {return false;
        }

        // The speed pointer
        ListNode slow = head;
        ListNode fast = head.next;

        // Stop the loop if the list is not a loop
        while(fast ! =null&& fast.next ! =null) {// Target hit, return result
            if(slow == fast){
                return true;
            }
            
            // Move the pointer
            slow = slow.next;
            fast = fast.next.next;
        }

        / / not to ring
        return false; }}Copy the code