Scribd
Upload
45 views7 pages

Two Pointers Algorithm in Java

The algorithm finds loops in linked lists by using two pointers - a slow pointer and a fast pointer. [1] The pointers are initialized at the head of the list and the fast pointer moves twice as fast as the slow pointer. [2] When the pointers meet, they will be inside the loop since the fast pointer will have completed one or more full loops. [3] The starting and length of the loop can then be determined based on the positions of the pointers.

Uploaded by

Aayush Tripati
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
45 views7 pages

Two Pointers Algorithm in Java

The algorithm finds loops in linked lists by using two pointers - a slow pointer and a fast pointer. [1] The pointers are initialized at the head of the list and the fast pointer moves twice as fast as the slow pointer. [2] When the pointers meet, they will be inside the loop since the fast pointer will have completed one or more full loops. [3] The starting and length of the loop can then be determined based on the positions of the pointers.

Uploaded by

Aayush Tripati
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Flgas Ggede

Finding Algorithr
Floy's gcle fnding Algorithy isavong wsedi
algoithim, os the þnposes
in inkRed dists.
inding dooks
Jaentijgin3 +hese oops is impo tant othewiSe
Se can tavese
inintey intthe loop.
inenr oat
ABeoped
linkei

loop past
The Algosi thm also solves tuso other þoblema
* Finding the stort he loop.
* Fnding the leng the loep.
Fe Agosithm -’ ) lnihalize tso þointes ostt
slespt
2 lncyemet oetptr too nsdes
ahend cohde glo ptr ene
mode ahead
3) theg meet ot Sone point,
loop e isb, oAhersise doesn
Fo indng stot doop (assuming Loof eaisS)’
)nce the tso pointers meet, initilize slousptr
Gok to head o imked diot again
2) Naco make looth lap 8cstpt move at e
made atime.
3) The point ohere themeet will be the stast
4he Seop.

" Fon inding deng t locf


1) Alter gou id start node g koof heep
incsementing datfpt one
one nod
node t atme

wlile Keeping slsupt staienay *


2) heep tack n counter, incremening it
evey fime o new node is tavesed in
(Initi alie conter to o)

3)enee gov
you make ost ptr meet slasr
ayain, he COUnter yarias le value
is the length o the doop
PRoF OF CORRECTNESS OF ALGORITHNS ,2,3.

) Assome the list to have a total n nodes


with e nodes in inear ast and
m hodes in Aocp pat.
| ast node inear past is censidesed
By lni tiolizing slaw
since dost (my
seS twice at the speed
las;
Hence cohile slans covers nodeg to
reach O Cmod m)
Covers the nodes in inear þart
and then nodes into loo:
sles o (mod m)
mod

need to shew thot theg wil


meet at semefointin the loob hile
they go aroond in cie les.
:. Te t st

t = lt2t(mod )
Sost
ptr
þositen peitien
ln lact ets ty and frove a mOre

genenl ormie

Totind condition existence


t , st

(P-)t (k-kkmdm)
Neo or 30ch t to eris
t must Ge a n
integer,

(p-)\k-K)
cannot divide
But oe
ha-) witn (-) heres

diwdng y 6= I(modo)
4 which iS

obuious Sy olse.
Houseves, oting it os
24 = 4 t a0cK)
Geing3
dividing y
6 +
6 1mods) ’ which is frue
gdlk-v, m) = a

(ha-t) is divisible Cm(-)


holdy
Su ch a tt e ists

t l+2t mod m)

(P-v)
Bcth conditiens
Satiagied.
t - modm)
addittve invee
modulaY Syatem nodm
the tuoo bointens
4hese ma
willmeet

EXACTLY steps latey


(mz
(me)
(t-A (nodm))
his algo maes sense Gec ause
to ex\st
ostpt would ench end a ist
whi de slet oute oe a

a) To ind Sort node


ptr's
cshen the tuoo nodes mee

t= lt * modm)
t o modm)
by int adizing elau btr to heod
and mahe t taved ene node at
atime, ohile eled t is at
Joat
+24 mod m
and mahe t increment at ene þositien
at a ttime to,
By the time Slas bointes traueds
nods to reach O(medm)

positien nodes in the oc


Gut alltt) =o(mod m)
Botth uoill oneet at ivst node of
Qoof omcd m)
is tivil

mi omodm)
Hence poved.

You might also like