Grind 75 Question 13: Linked List Cycle
Another linked list to close out Week 1!
The Problem
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.
The Initial Attempts
This looks like a fast-and-slow pointer problem, but I need to review my 14 Leetcode Patterns notes before I decide how to approach it on the whiteboard. Yes — the answer is yes. This problem is given as an example of the fast-and-slow pointer approach. Now…to actually implement it.
I realize quickly that I’m not even sure how to use two pointers in a linked list where all you can see is head and head.next. But I give it the old college try and come up with this:
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
let slowPointer = 0;
let fastPointer = 0;
while(head) {
slowPointer += 1;
fastPointer += 2;
if(head[slowPointer] === head[fastPointer]) return true;
}
return false;
};It…returns accepted. Without any modifications or curly braces. So I throw more tests at it and…nerp. The non-cyclic list returns true. Some investigating reveals that I’m returning undefined and undefined, so of course they’re always going to match each other. Back to the drawing board. Or…Neetcode.
The Solution
Okay, it turns out I wasn’t that far off. I wasn’t that close either, but hey. I refuse to be discouraged. I just needed to know how to manipulate a linked list. And now, I have that knowledge! Behold:
var hasCycle = function(head) {
let fastPointer = head;
let slowPointer = head;
while(fastPointer && fastPointer.next) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next.next;
if(slowPointer == fastPointer) return true;
}
return false;
};Pretty easy, once you figure it out:
- First, we declare a fast pointer and a slow pointer. Tortoise and hare! Er. Hare and tortoise.
- Next, we run our while loop: while fastPointer and fastPointer.next exist (which they always will if it’s a cyclic linked list)
- Move slowPointer one to the right
- Move fastPointer two to the right — see what we did there? .next.next!
- If slowPointer and fastPointer are at the same spot, break out of the cycle and return true.
- If we get to the end of the linked list and the pointers haven’t met, that’s it! The list isn’t cyclic. Return false.
What I Learned
- The tortoise and hare algorithm! Apparently it’s a popular one. I was almost there, just…not quite.
- How to move faster through a linked list! .next.next ad infinitum, I’m sure.
And that’s it for Week 1! It’s only taken me…two weeks to complete! NBD. Although, I am speeding up a bit — really trying to time box and read through the solution if I’m not getting it after the initial whiteboarding and tweaking. If I keep going at a rate of 2/day I will make it through Week 2 by this time next week. I’ve got this. I’m having fun. I’m only starting, baby.
mins
read
