Conas a bhraitheonn tú timthriall le tortoise agus hainnir Floyd?

Question

IT Interview Practice · Accepted Answer

**Braistint timthriall Floyd** faigheann sé lúb i seicheamh (cosúil le liosta ceangailte) ag baint úsáide as dhá phointéir ag gluaiseacht ar luasanna difriúla. Má bhíonn timthriall ann, baineann an pointéir tapa agus bhuaileann sé ar an pointéir mall ar deireadh. Úsáideann sé **O(1)** spás breise.

## An smaoineamh

Bogadh pointéir **slow** ar feadh céim amháin agus pointéir **fast** ar feadh dhá chéim. I timthriall, laghdaítear an bhearna le ceann gach céim, caithfidh siad imbhualadh mar sin; gan timthriall, sroichfidh fast an deireadh.

## Sampla

```python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # +1 step
        fast = fast.next.next       # +2 steps
        if slow is fast:            # pointers met -> cycle
            return True
    return False                    # fast hit the end -> no cycle
```

## Castachta

- **Am:** O(n). **Spás:** O(1).

Oibríonn cur chuige hash-set freisin ach cosnaíonn sé O(n) spás; úsáideann Floyd's spás tairiseach.

## Cathain a úsáid / pothanna

Úsáid do **bhraistint timthriall liosta ceangailte**, teacht ar thús an timthriall, agus timthriallanna a bhraistint i ngraif fheidhmiúil (tá comharbhaí amháin ag gach nód). Bíodh cosaint i gcónaí ar `fast.next` chun diúltú do dhílíonadh null. I ndáil le graif ghinearálta, úsáid DFS le stac athchúrsála ina ionad sin.

## Cén fáth atá sé tábhachtach

Tá braistint timthriall riachtanach do thrasnú sábháilte — ciallaíonn lúb neamhbhraiste athrá gan críoch.

Is sampla dea-dhéanta é algartam Floyd ar fhadhb O(n)-spás a réiteach i O(1) spás le invariant cliste.

Tagann sé i gceist in agallamh liosta ceangailte agus i bhraistint ar lúba gan chríoch i meisiúin stáit agus seichimh uimhreach.

An smaoineamh

Sampla

Castachta

Cathain a úsáid / pothanna

Cén fáth atá sé tábhachtach

Ceisteanna gaolmhara