Linked lists and Piano Scales

What if the list links back to itself and is a cycle?Our poor runner could just go on running forever in circles!var head = ListNode(5)head.

next = ListNode(7)let secondNode = head.

nexthead.

next?.

next = ListNode(8)head.

next?.

next?.

next = ListNode(12)head.

next?.

next?.

next?.

next = secondNodeThen you need not one helper, but two, a tortoise and a hare.

In this case the hare will go two ahead at a time, twice as fast as the tortoise.

We all know that rabbits are faster than turtles, right?(Although in faraway lands, tortoises have been known to invent strange machines and eventually outrun the hare… but let’s not get ahead of ourselves.

)For this case we also assume that no nodes have the same value in the list.

Maybe they are each unique, like values in a Bitcoin Merkel Tree.

Maybe they are unique numbers showing your DNA, which belongs to you and only you.

We let both our hare and our tortoise start at the beginning of the list.

var tortoise = headvar hare = headThe hare goes two ahead at a time:while let hareNext = hare.

next?.

next, let tortoiseNext = tortoiseNext.

nextIf either hareNext or tortoiseNext is nil, then we know we are at the end.

We’ll break out of the while loop.

But since this is a cycle, that will not happen!.They will just keep going on forever and ever, unless the rabbit catches up with the hare… which it does!if hare.

val == tortoise.

val { return true}Quite clever, isn’t it?.It’s moments like these that open the door to more and more clever tricks, and starting from here algorithms become less painful and start to get very fun!But before you can start to compose your own music, and before you can meet other musicians and jam, sometimes you have to practice your scales first and learn your lessons.

You’ll get there!These places led the way for me:RayWenderlich Swift Algorithm Club they have a cool video series now too!.And they have a book and video series too.

Going to a meetup with like-minded people at the Noisebridge Hackerspace and Women Who Code SF — preferably near walkable public transportationAnd it’s nice to watch videos but it’s best to do code itself, so I’ve been having fun with LeetCode and Hackerrank.. More details

Leave a Reply