Long street, fireworks fan, you look back. This article was first published on the public account “Mushroom can’t sleep”, more exciting content welcome to pay attention to

1. Title Description

Given a linked list, determine whether 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, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note: POS is not passed as an argument, just to identify the actual state of the linked list.

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

Example 1:

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

Example 2:

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

Example 3:

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

Tip:

  • The number of nodes in the list ranges from 0 to 104.
  • -105 <= Node.val <= 105
  • Pos is -1 or a valid index in a linked list.

Ii. Analysis of Ideas:

If a linked list has rings, then a fast pointer and a slow pointer will overlap at some node in the future. This is just like a long-distance race in the playground, because the playground is closed loop, the fast one will meet and overtake the slow one in a short time, so we can use this idea to judge that the linked list has rings. The code is as follows:

AC code

public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } // block pointer ListNode slow = head; ListNode fast = head. Next; ListNode fast = head. // When two nodes do not intersect while (slow! = fast) {/ / when the pointer traverse quickly to end all have no intersection, show that no ring if (fast = = null | | fast. The next = = null) {return false. } slow = slow.next; fast = fast.next.next; } return true; }}Copy the code

Time complexity: O(N), where N is the number of nodes in the linked list. Space complexity :O(1).

Four,

This problem also needs the help of certain life knowledge, running circle theory can be fully applicable to this problem, the way of fast and slow pointer can perfectly solve the problem of whether the linked list has a ring.

If you think the article is good, just click a like, close a note bai ~