[leetcode] [python] 142. Linkitetty luettelosykli II

142




Knowledge points: two pointers

1. Alkuperäinen nimi

Palauta solmu, josta jakso alkaa, linkitetyn luettelon perusteella. Jos jaksoa ei ole, palauta nolla.



Esitämme sykliä annetussa linkitetyssä luettelossa käytämme kokonaislukua pos, joka edustaa linkitetyn luettelon sijaintia (0-indeksoitu), johon pyrstö liittyy. Jos pos on -1, linkitetyssä luettelossa ei ole sykliä.



Huomaa: Älä muokkaa linkitettyä luetteloa.



Esimerkki 1:

Syöttö: pää = [3,2,0, -4], pos = 1
Lähtö: häntä yhdistetään solmuindeksiin 1
Selitys: Linkitetyssä luettelossa on sykli, jossa pyrstö muodostaa yhteyden toiseen solmuun.

Esimerkki 2:



Syöttö: pää = [1,2], pos = 0
Lähtö: häntä yhdistetään solmuindeksiin 0
Selitys: Linkitetyssä luettelossa on sykli, jossa pyrstö muodostaa yhteyden ensimmäiseen solmuun.

Esimerkki 3:

Syöttö: pää = [1], pos = -1
Lähtö: ei jaksoa
Selitys: Linkitetyssä luettelossa ei ole sykliä.

Seuranta:
Voitko ratkaista sen käyttämättä ylimääräistä tilaa?

2. Otsikko

Arvioi onko listassa rengas, jos on, palaa muuten renkaan alkupisteeseen, palaa Ei mitään

3. Ideoita

Jos vain päätät onko renkaasta, voit saada nopean osoittimen siirtymään kaksi askelta kerrallaan ja hitaan osoittimen yksi askel kerrallaan. Niin kauan kuin kaksi osoitinta ovat samat, on rengas.
Mutta jos sinun on löydettävä renkaan alkupiste, sinun on analysoitava se. (Kuva on Nan Guo Ziqiltä, ​​kiitos paljon)
kuva
Ensinnäkin, hyväksy ajatus kahdesta vaiheesta nopeammin ja yksi vaihe hitaammin, niin että kaksi osoitinta kohtaavat selvittääkseen onko renkaassa kuvassa kohtaamispaikka. Kokouksen aikaan hidas osoitin kulkee k + M: n matkan, kun taas nopea osoitin k + M + n L: n, n: n etäisyys on kierrosten määrä mennä enemmän.
2 (k + M) = k + M + n
L
k = n * L - M
Joten kokouksen jälkeen laita hidas osoitin takaisin päähän, ja nopea osoitin pysyy kohtaamispaikassa edustamaan vähennettyä etäisyyttä M. Sen jälkeen nopeat ja hitaat osoittimet otetaan askel askeleelta. Kun kaksi osoitinta kohtaavat, se on lähtökohta.

4. Koodi

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def detectCycle(self, head): ''' :type head: ListNode :rtype: ListNode ''' if head==None or head.next==None: return None f=s=head while f and f.next: f=f.next.next s=s.next if f==s: break if f==s: s=head while f!=s: f=f.next s=s.next return s return None

5. Viite

https://www.cnblogs.com/zuoyuan/p/3701877.html