This is the third day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

describe

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Copy the code

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Copy the code

Example 3:

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

Note:

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.
Copy the code

parsing

Let’s check if there are any rings in the linked list.

They also give the definition of a loop: a linked list has a loop if there is a node that can be reached again by the next pointer in succession. The pos variable is used to represent the index of the node to which tail’s next pointer is connected. Note that pos is not passed as an argument.

If we can, they’re going to go even further, let’s use constant level memory.

In fact, the solution to determine whether there is a ring on the linked list is usually fixed. It is to find a fast pointer FAST and a slow pointer, and make FAST move forward two steps at a time, and slow move forward one step at a time. If there is a ring in the linked list, then FAST will definitely meet slow again.

answer

class ListNode(object): def __init__(self, x): self.val = x self.next = None class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ slow = head fast = head while fast! =None and fast.next! =None : slow = slow.next fast = fast.next.next if slow == fast: return True return FalseCopy the code

The results

Linked List Cycle in the Linked List given in the Linked submissions. Submissions in Python online submissions for Linked List Cycle.Copy the code

Original link: leetcode.com/problems/li…

Your support is my biggest motivation