Repeat Code With LeetCode — Linked List Cycle
Tonight, Aesop helps us with LeetCode
I was about to write about how this problem is popular without good reason, but the Wikipedia page alone confirms that the algorithm has applications in pseduo-random number generation, cryptography, and cellular automaton. It’s certainly popular in interviews, so much so that it’s even one of the 14 coding patterns. I’ve even heard that it was used on new college graduates at my own company.
The Problem
Difficulty: Easy
Skills Required: Linked lists
Description: 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 continuously following the next pointer. Internally, pos is used to denote 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.
Explanation
I know this is a really popular interview question, but I still have trouble seeing how it is useful for determining whether or not someone is a competent programmer.
The solution is to use a coding pattern called “fast and slow pointers.” Your fast pointer moves twice as fast as your slow pointer.
If you want to see whether a linked list has a cycle, set your fast pointer and slow pointer to head (or one “step” after, depending on implementation). If there is no cycle, you will hit the end and be able to terminate your program. If there is a cycle, then your fast pointer and slow pointer will eventually meet.
The Solution
Last week I did a tree problem. A binary tree can degenerate to a linked list, and you may notice that these LeetCode linked list problems look a bit similar to binary tree problems. Like a binary tree node, these nodes consist of a simple struct that holds one piece of data. Unlike a binary tree node, this node only stores a reference to the next one (not a left and right child).
Start by setting the slow pointer and the fast pointer to head.
There’s a bit of short-circuit evaluation going on on line 16. You want to avoid a compiler error, and you want to only continue while the node to the right of your fast pointer exists. To do this you need to first check that the node one to the right exists, and to do that you need to first check that the fast pointer exists (is not null). In other words, line 16 is just a safe way to verify that fastPtr->next->next exists.
Nick White does it a little differently, but it is the same fundamental idea. The while loop above will move both pointers along, then do the check. Nick White starts them at their appropriate places one step ahead.
