package Ġle et code Ċ Ċ /** Ċ Ġ* Ġ# Ġ 1 4 1 . ĠLinked ĠList ĠCycle Ċ Ġ* ĠGiven Ġhead , Ġthe Ġhead Ġof Ġa Ġlinked Ġlist , Ġdetermine Ġif Ġthe Ġlinked Ġlist Ġhas Ġa Ġcycle Ġin Ġit . Ċ Ġ* Ċ Ġ* ĠThere Ġis Ġa Ġcycle Ġin Ġa Ġlinked Ġlist Ġif Ġthere Ġis Ġsome Ġnode Ġin Ġthe Ġlist Ġthat Ġcan Ġbe Ġreached Ġagain Ġby Ġcontinuous ly Ġfollowing Ġthe Ġnext Ġpointer . ĠIntern ally , Ġpos Ġis Ġused Ġto Ġden ote Ġthe Ġindex Ġof Ġthe Ġnode Ġthat Ġtail 's Ġnext Ġpointer Ġis Ġconnected Ġto . ĠNote Ġthat Ġpos Ġis Ġnot Ġpassed Ġas Ġa Ġparameter . Ċ Ġ* Ċ Ġ* ĠReturn Ġtrue Ġif Ġthere Ġis Ġa Ġcycle Ġin Ġthe Ġlinked Ġlist . ĠOtherwise , Ġreturn Ġfalse . Ċ Ġ* Ċ Ġ* Ġ## ĠExample Ġ 1 : Ċ Ġ* Ċ Ġ* Ġ``` Ċ Ġ* ĠInput : Ġhead Ġ= Ġ[ 3 , 2 , 0 ,- 4 ], Ġpos Ġ= Ġ 1 Ċ Ġ* ĠOutput : Ġtrue Ċ Ġ* ĠEx planation : ĠThere Ġis Ġa Ġcycle Ġin Ġthe Ġlinked Ġlist , Ġwhere Ġthe Ġtail Ġconnects Ġto Ġthe Ġ 1 st Ġnode Ġ( 0 - indexed ). Ċ Ġ* Ġ``` Ċ Ġ* Ċ Ġ* Ġ## ĠExample Ġ 2 : Ċ Ġ* Ġ``` Ċ Ġ* ĠInput : Ġhead Ġ= Ġ[ 1 , 2 ], Ġpos Ġ= Ġ 0 Ċ Ġ* ĠOutput : Ġtrue Ċ Ġ* ĠEx planation : ĠThere Ġis Ġa Ġcycle Ġin Ġthe Ġlinked Ġlist , Ġwhere Ġthe Ġtail Ġconnects Ġto Ġthe Ġ 0 th Ġnode . Ċ Ġ* Ġ``` Ċ Ġ* Ċ Ġ* Ġ## ĠExample Ġ 3 : Ċ Ġ* Ġ``` Ċ Ġ* ĠInput : Ġhead Ġ= Ġ[ 1 ], Ġpos Ġ= Ġ- 1 Ċ Ġ* ĠOutput : Ġfalse Ċ Ġ* ĠEx planation : ĠThere Ġis Ġno Ġcycle Ġin Ġthe Ġlinked Ġlist . Ċ Ġ* Ġ``` Ċ Ġ* Ċ Ġ* Ġ## ĠConstraints : Ċ Ġ* Ġ``` Ċ Ġ* ĠThe Ġnumber Ġof Ġthe Ġnodes Ġin Ġthe Ġlist Ġis Ġin Ġthe Ġrange Ġ[ 0 , Ġ 1 0 4 ]. Ċ Ġ* Ġ- 1 0 5 Ġ<= ĠNode . val Ġ<= Ġ 1 0 5 Ċ Ġ* Ġpos Ġis Ġ- 1 Ġor Ġa Ġvalid Ġindex Ġin Ġthe Ġlinked - list . Ċ Ġ* Ġ``` Ċ Ġ* Ċ Ġ* ĠFollow Ġup : ĠCan Ġyou Ġsolve Ġit Ġusing ĠO ( 1 ) Ġ( i . e . Ġconstant ) Ġmemory ? Ċ Ġ*/ Ċ @ Suppress (" ClassName ") Ċ class Ġ` 1 4 1 _ Linked _ List _ Cycle ` Ġ{ ĊĊĠ Ġclass ĠListNode ( var Ġ` val `: ĠInt ) Ġ{ ĊĠĠĠ Ġvar Ġnext : ĠListNode ? Ġ= Ġnull ĊĠ Ġ} ĊĊĠ Ġclass ĠSolution Ġ{ ĊĠĠĠ Ġfun Ġhas Cycle ( head : ĠListNode ?): ĠBoolean Ġ{ ĊĠĠĠĠĠ Ġif Ġ( head ?. next Ġ== Ġnull ) Ġreturn Ġfalse ĊĊĠĠĠĠĠ Ġvar Ġslow Ġ= Ġhead ĊĠĠĠĠĠ Ġvar Ġfast Ġ= Ġhead . next ĊĊĠĠĠĠĠ Ġwhile Ġ( slow Ġ!= Ġfast ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( fast ?. next Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġslow Ġ= Ġslow ?. next ĊĠĠĠĠĠĠĠ Ġfast Ġ= Ġfast . next ?. next ĊĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĠ Ġ} Ċ }