LeetCode Meditations: Linked List Cycle

Let's start with the description for Linked List Cycle:

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.

For example:

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).

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).

One easy way to do it is using a set. As we traverse the list, we can look up each node in the set, and if it's there, we know that there has to be a cycle so we can just return true.

Here is how it looks like in TypeScript:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.next = (next === undefined ? null : next)
 *   }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
  let nodes = new Set();
  let currentNode = head;

  while (currentNode !== null) {
    if (nodes.has(currentNode)) {
      return true;
    }
    nodes.add(currentNode);
    currentNode = currentNode.next;
  }

  return false;
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.next = (next === undefined ? null : next)
 *   }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
  let nodes = new Set();
  let currentNode = head;

  while (currentNode !== null) {
    if (nodes.has(currentNode)) {
      return true;
    }
    nodes.add(currentNode);
    currentNode = currentNode.next;
  }

  return false;
};

Time and space complexity

The time complexity of this solution is $O(n)$ as we go through every node in the list once. The space complexity is also $O(n)$ because we'll store each node in nodes, and its size will grow with the size of the linked list.

There is another way to solve this problem that is more memory efficient using fast and slow pointers, where we don't need to store an additional data structure at all:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.next = (next === undefined ? null : next)
 *   }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }   

  return false;
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.next = (next === undefined ? null : next)
 *   }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }   

  return false;
};

We initialize both pointers at the head, and while fast (or its next pointer) is not null, we'll update them. Of course, while slow is moving one step at a time, fast is increasing by two steps. And, we return true if they both point to the same node, at which point we know there has to be a cycle. Otherwise, if fast ever points to null, we know that there is no cycle, so we can return false.

This technique of detecting a cycle is also called Floyd's tortoise and hare algorithm.

The important thing is that when slow and fast catch up, they are going to be pointing to the same node. The reason that this works is that while slow increases the distance between it and fast by 1, fast decreases that distance by 2 — eventually making the overall distance between them 0.

It makes more sense with an example such as the one given in NeetCode's explanation.

Time and space complexity

The time complexity is $O(n)$ where $n$ is the length of the cycle (we can imagine a worst case scenario where the last node points to the head). The good thing is that the space complexity is $O(1)$ because we don't need an additional data structure that will grow with the size of the input.

The last problem in this chapter will be Merge K Sorted Lists. Until then, happy coding.

Eda Eren

LeetCode Meditations: Linked List Cycle

Time and space complexity

Time and space complexity