Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to realize the circular linked list in python". In the operation of the actual case, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

[title]

Given a linked list, determine whether there are rings in the linked list.

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. To represent the rings in a given linked list, we use the integer pos to indicate where the tail of the linked list is connected to the linked list (the index starts at 0). If pos is-1, there are no rings in the linked list. Note: pos is not passed as a parameter, only to identify the actual situation of the linked list.

Returns true if there is a ring in the linked list. Otherwise, return false.

Advanced:

Can you solve this problem with O (1) (that is, constant) memory?

Example 1:

Input: head = [3Pere2Person0Lay 4], pos = 1 output: true explanation: there is a ring in the linked list, its tail is connected to the second node.

Example 2:

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

Example 3:

Input: head = [1], pos =-1 output: false explanation: there are no rings in the linked list.

Tip:

The number of nodes in the linked list ranges from [0104] to 105 n ·m-n is the number of laps of the fast pointer relative to the slow pointer)

The starting position of the ring, the corresponding advance number is a, then: a = (m-2n) * c-b

Furthermore, we get: a = (m-2n + 1) * c + (c-b)

So, the slow pointer goes back to head, and both pointers move only one step at a time, so the meeting point is the starting point of the ring.

Code:

# Definition for singly-linked list.

# class ListNode:

# def _ _ init__ (self, x):

# self.val = x

# self.next = None

Class Solution:

Def detectCycle (self, head: ListNode)-> ListNode:

# find the meeting point

Fast, slow = head, head

Flag = False # No ring

While fast:

If fast and fast.next:

Fast = fast.next.next

Slow = slow.next

Else:

Break

If fast = = slow:

Flag = True

Break

If not flag:

Return None

# step = a + b + n * c (an is the number of elements before entering the ring; b is the number of remaining steps, c is the number of elements in the ring)

# 2 * step = a + b + m * c (m > ndirection m-n is the number of laps of the fast pointer relative to the slow pointer)

# = > a = (m-2n) * c-b

# a = (m-2n + 1) * c + (c-b)

# the slow pointer returns to head, and both pointers move only one step at a time, so the meeting point is the starting point of the ring

Slow = head

While fast! = slow:

Fast = fast.next

Slow = slow.next

Return fast

This is the end of the content of "how to realize the circular linked list in python". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.