Two pointers walk the same linked list — one moves a node at a time, the other two nodes at a time. If the list loops, fast laps slow and they land on the same node. If it doesn't loop, fast simply runs off the end.
← Back to the Field GuideIkkita pointer bitta linked list bo'ylab yuradi — biri bir vaqtda bitta node, ikkinchisi bir vaqtda ikkita node bosib o'tadi. Agar list loop hosil qilsa, fast pointer slow'ni aylanib o'tadi va ular bir xil node'da uchrashadi. Loop bo'lmasa, fast list oxiriga yetib to'xtaydi.
← Qo'llanmaga qaytishWatch the loop below: the solid ring is the tortoise, the dashed ring is the hare, moving twice as fast. On a straight path the hare would simply vanish off the end — but inside a loop, the gap between them shrinks every step until they land on the same node.
Quyidagi loop'ga qarang: to'liq halqa — toshbaqa, shtrixli halqa esa undan ikki baravar tez harakatlanadigan quyon. To'g'ri yo'lda quyon oxirigacha yetib g'oyib bo'lar edi — lekin loop ichida ular orasidagi masofa har qadamda qisqarib, oxir-oqibat bir xil node'da uchrashadi.
slow = head, fast = head. Both begin on the same node — that's fine, since the comparison that matters happens after they've moved.fast at all: while fast is not None and fast.next is not None. Both parts matter — advancing fast is about to require two .next hops, and either one can blow up if the node in front of it is None.slow = slow.next.fast = fast.next.next — the first hop lands on fast.next (already known not to be None from the guard), the second hop is only safe because that node was reachable through a real node too.slow is fast, they now sit on the exact same node — that can only happen if some path led fast back around to a node slow already occupies, i.e. a cycle. Return True immediately.fast and fast.next before either pointer moves again.while condition eventually fails — fast lands on None, or fast.next is None — the list ran out of nodes without slow and fast ever coinciding, so there's no cycle: return False.slow = head, fast = head. Ikkalasi bitta node'dan boshlanishi muhim emas — ahamiyatli solishtirish ular harakatlangandan keyin sodir bo'ladi.fastga tegishdan oldin loop shartini tekshiring: while fast is not None and fast.next is not None. Ikkala qism ham muhim — fastni siljitish ikkita .next qadamini talab qiladi, va agar oldingi node None bo'lsa, ulardan har biri xatoga olib kelishi mumkin.slow = slow.next.fast = fast.next.next — birinchi sakrash fast.nextga tushadi (guard orqali None emasligi allaqachon ma'lum), ikkinchi sakrash esa o'sha node ham haqiqiy node orqali yetib bo'lgani uchungina xavfsiz.slow is fast bo'lsa, ular endi aynan bitta node'da turibdi — bu faqat fast biror yo'l orqali slow allaqachon turgan node'ga aylanib qaytganda, ya'ni cycle mavjud bo'lgandagina sodir bo'lishi mumkin. Darhol True qaytaring.fast va fast.next qayta tekshiriladi.while sharti bajarilmasa — fast Nonega yetsa yoki fast.next None bo'lsa — list slow va fast hech qachon bir-biriga to'g'ri kelmasdan tugagan, demak cycle yo'q: False qaytaring.Time: O(n). Consider two cases. If there's no cycle, fast is racing toward the end of the list at twice slow's speed, so it reaches the last node (or None) after roughly n/2 steps — a single pass, linear in the number of nodes. If there is a cycle, once both pointers have entered the loop (which takes at most n steps for the slower one to get there), the gap between them shrinks by exactly one node every step — fast covers 2 nodes, slow covers 1, so the net change in the gap is 1 per step — so a gap that starts somewhere between 0 and the cycle's length must close to zero within at most that many additional steps. Either way, the total number of steps is bounded by a small multiple of n, so runtime is O(n) — no nested loop, no revisiting the same ground more than a constant number of times.
Space: O(1). The algorithm only ever holds two pointer variables, slow and fast — it never builds a set of nodes it's already seen the way a hash-set-based cycle check would, so memory use doesn't grow no matter how long the list — or its cycle — is.
Vaqt: O(n). Ikki holatni ko'rib chiqing. Agar cycle bo'lmasa, fast list oxiriga slow'dan ikki baravar tez tomon yuguradi, shuning uchun taxminan n/2 qadamdan so'ng oxirgi node'ga (yoki Nonega) yetadi — bitta pass, node'lar soniga nisbatan chiziqli. Agar cycle bo'lsa, ikkala pointer loop'ga kirgandan so'ng (buning uchun sekinroq pointer'ga ko'pi bilan n qadam kerak), ular orasidagi masofa har qadamda aynan bitta node'ga qisqaradi — fast 2 ta, slow 1 ta node bosib o'tadi, shuning uchun masofaning sof o'zgarishi har qadamda 1 ta — demak, 0 bilan cycle uzunligi orasida boshlangan masofa ko'pi bilan shuncha qo'shimcha qadamda nolga tushishi shart. Ikkala holatda ham jami qadamlar soni n'ning kichik karralisi bilan chegaralangan, shuning uchun runtime O(n) — nested loop yo'q, bir xil joy bir necha martadan ortiq (o'zgarmas songa qadar) qayta bosib o'tilmaydi.
Xotira: O(1). Algoritm faqat ikkita pointer o'zgaruvchisini — slow va fastni — saqlaydi; u hech qachon ko'rilgan node'lar to'plamini (hash-set asosidagi cycle tekshiruvi qiladigandek) qurmaydi, shuning uchun list — yoki uning cycle'i — qanchalik uzun bo'lishidan qat'i nazar xotira sarfi o'smaydi.
while fast: and then running fast = fast.next.next unconditionally. Fix: guard both hops with while fast and fast.next: — if fast has already reached the last node, fast.next is None, and fast.next.next tries to read .next off None, crashing with an AttributeError before the loop even gets to compare pointers.slow is fast before either pointer has moved at all — since both start at head, that condition is trivially true on entry, which would report a cycle even on a list that plainly doesn't have one. Fix: only compare after advancing both pointers inside the loop body, never before the first move.slow.val == fast.val) instead of comparing the nodes themselves. Fix: compare identity — slow is fast — because two distinct nodes can legitimately hold equal values without being the same node, which would produce a false positive.fast by one node just like slow, or by three nodes instead of two. Fix: keep the classic 1-step/2-step ratio; it's exactly what guarantees the gap between the pointers shrinks by one node every step once both are inside a cycle, which is what forces them to land on the same node instead of skipping past each other.while fast:ni tekshirib, keyin fast = fast.next.nextni shartsiz bajarish. Yechim: ikkala sakrashni ham while fast and fast.next: bilan qo'riqlang — agar fast allaqachon oxirgi node'ga yetgan bo'lsa, fast.next None bo'ladi, va fast.next.next Nonening .nextini o'qishga urinib, loop pointer'larni solishtirishga yetmasdanoq AttributeError bilan qulaydi.slow is fastni solishtirish — ikkalasi ham headdan boshlangani uchun bu shart kirishda avtomatik to'g'ri bo'ladi, bu esa aslida cycle bo'lmagan list'da ham cycle borligini xabar qiladi. Yechim: faqat loop tanasida ikkala pointer ham harakatlangandan keyin solishtiring, birinchi harakatdan oldin hech qachon emas.slow.val == fast.val) solishtirish. Yechim: identity'ni solishtiring — slow is fast — chunki ikkita alohida node bir xil node bo'lmasdan ham qonuniy ravishda teng qiymatlarga ega bo'lishi mumkin, bu esa noto'g'ri musbat natija beradi.fastni ham slow kabi bitta node siljitish, yoki ikkita o'rniga uchta node siljitish. Yechim: klassik 1-qadam/2-qadam nisbatini saqlang; aynan shu nisbat ikkala pointer cycle ichiga kirgandan so'ng ular orasidagi masofa har qadamda bitta node'ga qisqarishini kafolatlaydi — bu esa ularni bir-birini o'tkazib yubormasdan, aynan bitta node'da uchrashishga majbur qiladi.fast reaches the end, slow is standing exactly halfway.fast oxiriga yetganda, slow aynan yarmida turadi.Restated: given the head of a singly linked list, determine if the list has a cycle in it — meaning some node's next pointer eventually points back to a node earlier in the list, so the list never actually ends. Return True if there's a cycle, False otherwise, using only O(1) extra memory (no set of every node visited).
head. If the list is empty or has a single node with no self-loop, the loop guard fast and fast.next is simply false immediately (or after one check), so there's nothing extra to handle before the loop.slow one node and fast two nodes, guarded by while fast and fast.next.slow is fast, a cycle exists — return True right away, no need to keep going.fast (or fast.next) ever becomes None, the list ran out of nodes without a meeting, so return False.def hasCycle(head):
# head is a ListNode (or None); ListNode has .val and .next,
# as provided by LeetCode's linked list definition.
slow, fast = head, head
while fast and fast.next:
slow = slow.next # tortoise: one node per step
fast = fast.next.next # hare: two nodes per step
if slow is fast: # they can only coincide if fast looped back onto slow
return True
return False # fast (or fast.next) hit None: list has a real end, no cycle
Qayta bayon: singly linked list'ning headi berilgan — list'da cycle bor-yo'qligini aniqlang, ya'ni biror node'ning next pointer'i oxir-oqibat list ichidagi avvalgi node'ga qaytib bog'lanadimi, shu sababli list aslida hech qachon tugamaydimi. Cycle bo'lsa True, bo'lmasa False qaytaring — faqat O(1) qo'shimcha xotira bilan (ko'rilgan har bir node'ning to'plami saqlanmasdan).
headdan boshlang. Agar list bo'sh bo'lsa yoki o'z-o'ziga loop qilmaydigan bitta node'dan iborat bo'lsa, fast and fast.next loop shartning o'zi darhol (yoki bir tekshiruvdan keyin) noto'g'ri bo'ladi, shuning uchun loop'dan oldin qo'shimcha hech narsa hal qilish shart emas.slowni bitta node, fastni ikkita node siljiting, while fast and fast.next bilan qo'riqlangan holda.slow is fast bo'lsa, cycle mavjud — darhol True qaytaring, davom etish shart emas.fast (yoki fast.next) qachondir None bo'lib qolsa, list uchrashuvsiz tugagan, demak False qaytaring.def hasCycle(head):
# head is a ListNode (or None); ListNode has .val and .next,
# as provided by LeetCode's linked list definition.
slow, fast = head, head
while fast and fast.next:
slow = slow.next # tortoise: one node per step
fast = fast.next.next # hare: two nodes per step
if slow is fast: # they can only coincide if fast looped back onto slow
return True
return False # fast (or fast.next) hit None: list has a real end, no cycle
while fast and fast.next: — checking fast alone would leave fast.next.next unguarded whenever fast happens to be the last node (whose .next is None); reading .next off that None crashes with an AttributeError. Checking fast.next too guarantees both hops inside fast = fast.next.next land on real nodes — or the loop stops safely before either hop is attempted.while fast and fast.next: — faqat fastning o'zini tekshirish, fast oxirgi node bo'lib qolgan holatda (uning .nexti None) fast.next.nextni qo'riqlanmay qoldiradi; Nonening .nextini o'qishga urinish AttributeError bilan qulaydi. fast.nextni ham tekshirish fast = fast.next.next ichidagi ikkala sakrash ham haqiqiy node'larga tushishini kafolatlaydi — aks holda loop har ikkala sakrash sinalmasdan oldin xavfsiz to'xtaydi.