DEV Community

Cover image for LeetCode Meditations: Linked List Cycle
Eda
Eda

Posted on • Originally published at rivea0.github.io

1

LeetCode Meditations: Linked List Cycle

Make sure to check out the Fast & Slow Pointers post first!


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:

Example image

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).
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

Time and space complexity

The time complexity of this solution is O(n)O(n) as we go through every node in the list once. The space complexity is also O(n)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;
};
Enter fullscreen mode Exit fullscreen mode

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)O(n) where nn 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)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.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

11 Tips That Make You a Better Typescript Programmer

typescript

1 Think in {Set}

Type is an everyday concept to programmers, but it’s surprisingly difficult to define it succinctly. I find it helpful to use Set as a conceptual model instead.

#2 Understand declared type and narrowed type

One extremely powerful typescript feature is automatic type narrowing based on control flow. This means a variable has two types associated with it at any specific point of code location: a declaration type and a narrowed type.

#3 Use discriminated union instead of optional fields

...

Read the whole post now!

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay