[leetcode] [python] 142. Lingitud loenditsükkel II

142

---

Knowledge points: two pointers

1. Algne pealkiri

Seotud loendi korral tagastage sõlm, kust tsükkel algab. Kui tsüklit pole, tagastage null.

Tsükli kujutamiseks antud lingitud loendis kasutame täisarvu pos, mis tähistab lingitud loendis asukohta (0-indekseeritud), kuhu saba ühendub. Kui pos on -1, siis lingitud loendis tsüklit pole.

Märkus. Ärge muutke lingitud loendit.

Näide 1:

Sisend: pea = [3,2,0, -4], pos = 1
Väljund: saba ühendub sõlme indeksiga 1
Selgitus: Lingitud loendis on tsükkel, kus saba ühendub teise sõlmega.

Näide 2:

Sisend: pea = [1,2], pos = 0
Väljund: saba ühendub sõlmeindeksiga 0
Selgitus: Lingitud loendis on tsükkel, kus saba ühendub esimese sõlmega.

Näide 3:

Sisend: pea = [1], pos = -1
Väljund: tsüklit pole
Selgitus: lingitud loendis pole tsüklit.

Järelmeetmed:
Kas saate selle lahendada ilma lisaruumi kasutamata?

2. Pealkiri

Hinnake, kas loendis on rõngas, kui jah, naaske muidu sõrmuse alguspunkti, tagastage Puudub

3. Ideed

Kui otsustate lihtsalt, kas helin on olemas, saate panna kiire kursori minema kaks sammu korraga ja aeglase kursori üks samm korraga. Kuni kaks osutit on võrdsed, on rõngas.
Kuid kui peate leidma rõnga alguspunkti, peate seda analüüsima. (Pilt pärineb Nan Guo Ziqilt, suur aitäh)

Kõigepealt võtke mõte kaks sammu kiiremini ja üks aeglasemalt, nii et kaks näpunäidet kohtuvad, et teha kindlaks, kas pildil on kohtumispaik. Kohtumise ajal läbib aeglane kursor vahemaa k + M, kiire osuti aga k + M + n L, n kaugus on ringide arv, mida edasi minna.
2 （k + M） = k + M + n L
k = n * L - M
Nii et pärast kohtumist pange aeglane osuti tagasi pähe ja kiire kursor jääb kohtumispunkti, et tähistada lahutatud kaugust M. Pärast seda võetakse kiire ja aeglane osuti sammhaaval. Kui kaks osutit kohtuvad, on see lähtepunkt.

4. Kood

# 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. Viide

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