How Achilles overtakes the Tortoise in linked list

Achilles and the Tortoise is one of the Greek philosopher’s Zeno’s paradoxes.

In a race, the quickest runner can never overtake the slowest, since the pursuer must first reach the point whence the pursued started, so that the slower must always hold a lead. – as recounted by AristotlePhysics VI:9, 239b15

Which basically means that while the fast runner covers the distance that was between them at certain moment, the slowest goes a little farther, so the fast one has to overtake him again, and while he covers that (smaller) distance the slow one again goes on, and so the gap between them is always shortened but never disappears completely.

Recently I stumbled upon an interview question about singly linked list that made me recall this paradox.

How can you find the middle element of the list in ONE pass?

That is, not follow the list to the end to find out its size and then repeat from the beginning until you make half of the count. No, the question was to do it in just one go.

The solution to this task is to have two pointers, moving at the same time. The first would take one step, while the second would at the same time take two. When the second pointer reaches the end of the list, the first should be right in the middle. Such is the theory, and I think it is rather clever.

But what is the middle element of a list which has an even count? Is it null, or the last element in the first half, or the first element of the second?

I wish Zeno would answer that.

Advertisements

About Maryna Cherniavska

I have productively spent 10+ years in IT industry, designing, developing, building and deploying desktop and web applications, designing database structures and otherwise proving that females have a place among software developers. And this is a good place.
This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s