LeetCode 141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
This problem was labeled as easy on LeetCode but the follow-up was a little tricky to work around.
My approach was that I change the value in the given linked list to something unlikely (e.g. I used “@”) as I iterate through and if I encounter any “@” as a value in any node, the linked list is cyclic.
This works and passed all the test on LeetCode but it’s just not perfect because possibly “@” could be in a list and I destroy the original list. Making a copy of the list is out of the question as I have no extra space.
A solution on the discussion page had a nicer approach.
What I have understood from the code of the solution is:
Let two pointer iterate through a list in two different way
- One by one
- By skipping one node
In this way, the two pointers arrive at the same node if the list has a cycle. Otherwise, the pointer reaches null.
However, this was not really intuitive to understand. And I came up with better explanation.
Since one pointer moves two times faster than the other, the faster pointer goes through the cycle part at least twice or even more if only the part of the list is a cycle.
This algorithm actually has a name, “Floyd’s cycle-finding algorithm”.