Linked List Cycle

Patrick Leaton
Published: March 16, 2021, 12:09 a.m.
Problem 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.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

Constraints:

  • The number of the nodes in the list is in the range [0, 10^4].
  • -10^5 <= Node.val <= 10^5
  • pos is -1 or a valid index in the linked-list.

 

The description was taken from https://leetcode.com/problems/linked-list-cycle/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head is None or head.next is None:
            return False
        slow = head
        fast = head.next
        while slow != fast:
            if fast is None or fast.next is None:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

Problem Explanation

The first solution that may pop into our heads would be to store each number in a hashmap and return the number we see twice.

However, being a cycle detection problem, we can solve this by having a slow pointer that we would increment once each iteration and a fast pointer that we'd increment twice.  If the fast pointer takes a lap around the linked list track and smacks a "kick me" sign on the slow pointer's back, we know there is a cycle in the linked list.   

Let's start off by ensuring the head of the linked list and the first node are not null, we’ll return false if they are because there can't be a cycle if that's true.

        if head is None or head.next is None:
            return False

 

Next, we’ll initialize a slow pointer at the head and a fast pointer at head.next.  The condition that we are using to test if there is a cycle is if these two pointers are at the same node.  That is why we want to set the fast pointer one node past the slow pointer.

        slow = head
        fast = head.next

 

We’ll then create a loop that will run while the fast pointer hasn’t reached the slow pointer. 

        while slow != fast:

 

If the fast pointer has reached the end of the list we’ll return false because we’ll know there isn’t a cycle.

            if fast is None or fast.next is None:
                return False

 

Otherwise, we’ll increment the slow pointer by one node and the fast pointer by two. 

            slow = slow.next
            fast = fast.next.next

 

If the fast pointer has caught up to the slow pointer, we’ll break out of our loop and return true.  The hare lapped around and smacked the "kick me" sign on the shell of the tortoise.

        return True