current position：Home>142. Linked List Cycle II
142. Linked List Cycle II
2022-05-15 07:49:20【Sterben_ Da】
142. Linked List Cycle II
7195472Add to ListShare
head of a linked list, return the node where the cycle begins. If there is no cycle, return
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 (0-indexed). It is
-1 if there is no cycle. Note that
pos is not passed as a parameter.
Do not modify the linked list.
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.
Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.
Input: head = , pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.
- The number of the nodes in the list is in the range
-105 <= Node.val <= 105
-1or a valid index in the linked-list.
Follow up: Can you solve it using
O(1) (i.e. constant) memory?
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: """ Their thinking （ Others' ）： For the problem of finding loop in linked list , There is a general solution —— Speed pointer （Floyd Circle method ）. Given two pointers , Named as slow and fast, The starting position is at the beginning of the list . Every time fast Two steps forward ,slow Take a step forward . If fast You can go to the end , So there's no loop ; If fast You can go on forever , So there must be a loop , And must exist In a moment slow and fast meet . When slow and fast The first time I met , We will fast Move back to the beginning of the list , and Give Way slow and fast One step at a time . When slow and fast The second time we met , The node that meets is the starting point of the loop . """ slow = fast = head cycle = False while fast: slow = slow.next fast = fast.next if fast is None: return None if not cycle: fast = fast.next if slow == fast: if cycle or fast == head: # Second touch or already at the beginning return slow cycle = True fast = head continue return None
author[Sterben_ Da],Please bring the original link to reprint, thank you.
The sidebar is recommended
- Which securities company does qiniu school recommend? Is it safe to open an account
- Hyperstyle: complete face inversion using hypernetwork
- What activities are supported by the metauniverse to access reality at this stage?
- P2P swap OTC trading on qredo
- Google | coca: the contrast caption generator is the basic image text model
- SIGIR 2022 | Huawei reloop: self correcting training recommendation system
- Whether you want "melon seed face" or "national character face", the "face changing" technology of Zhejiang University video can be done with one click!
- Sorting of naacl2022 prompt related papers
- Servlet create project
- "Chinese version" Musk was overturned by the original: "if it's true, I want to see him"
guess what you like
[network security] web security trends and core defense mechanisms
[intensive reading] object detection series (10) FPN: introducing multi-scale with feature pyramid
007. ISCSI server chap bidirectional authentication configuration
plot_ Importance multi classification, sorting mismatch, image value not displayed
[intensive reading] object detection series (XI) retinanet: the pinnacle of one stage detector
How to install MFS environment for ECS
[intensive reading] the beginning of object detection series (XII) cornernet: anchor free
Open source sharing -- a record of students passing through time
MOT：A Higher Order Metric for Evaluating Multi-object Tracking
- How to develop a distributed memory database (1)
- Reverse engineers reverse restore app and code, and localization is like this
- One line command teaches you how to export all the libraries in anaconda
- Bi tools are relatively big. Let's see which one is most suitable for you
- Read the history of database development
- Self cultivation of coder - batterymanager design
- Technology application of swift phantom type phantom in Apple source code learning
- Swiftui advanced skills: what is the use of the technology of swift phantom type phantom
- Swiftui advanced animation Encyclopedia of complex deformation animation is based on accelerate and vector arithmetic (tutorial includes source code)
- What problems remain unsolved in swiftui in 2022
- I'll set the route for fluent
- Flutter drawing process analysis and code practice
- Emoji language commonly used icon collection (interesting Emoji)
- 5.14 comprehensive case 2.0 - automatic induction door
- How to deploy redis service on k8s top?
- Importance of data warehouse specification
- Idea automatically generates serialization ID
- Why is it recommended not to use select * in MySQL?
- Let's talk about why redis needs to store two data structures for the same data type?
- Domain lateral move RDP delivery
- [learn slam orb_slam2 or slam3 from scratch] summary of all blog articles
- 20000 + star ultra lightweight OCR system pp-ocrv3 effect increased by 5% - 11%!
- A configurable canvas clock - Super multi style
- The pp-ocrv3 effect of 20000 + star ultra lightweight OCR system is further improved by 5% - 11%
- MySQL's golden rule: "don't use select *"
- True interview question: why does redis store a data type twice?
- High threshold for large factories? Five exclusive PDFs inside Alibaba will take you forward and win the offer
- Is it really hard to find a job? How on earth can I find a job with high salary without worrying about being laid off
- How to design knowledge center? (code attached)
- OWASP top 10 vulnerability analysis
- Are you still writing comment templates manually? Idea can generate annotation templates of classes and methods with one click. Click in if you don't know
- Numpy core syntax and code sorting summary!
- Can you believe that the swoole timer can realize millisecond task scheduling?
- Detailed explanation of art template engine
- Telephone subsystem of openharmony source code analysis -- call flow
- Yixin Huachen: how to do a good job in digital transformation in the power industry?
- One stop collaboration is really delicious - apipost
- Notes on modern algebra and series of questions: Chapter 1 (introduction of algebraic system)
- Notes on modern algebra and serialization of question types: Chapter 2 (properties of binary operation)