5 minutes ago4 min read

141. Linked List Cycle - LeetCode Fastest Solution

Welcome back Code Recipian! Today, we'll tackle a popular coding interview question, LeetCode problem 141. Linked List Cycle.

If you are someone who is new to linked list data structure, we recommend you to go through our article on linked list fundamentals before proceeding further in this article.

This article is part of our LeetCode problem solutions series, so make sure to check out the other articles in this series once you are done with this one 😊.

Let's jump into the problem statement!

Problem Statement: Linked List Cycle

Given the head node of a singly linked list, determine if the linked list has a cycle in it. A linked list has a cycle if some node in the list can be reached again by continuously following the next pointer.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3, 2, 0, -4]

Output: true

Explanation: Linked list has a cycle, node with value -4 connects back to the 2nd node with value 2.

Example 2:

Input: head = [1, 2, 3, 4]

Output: false

Explanation: Given linked list does not have a cycle.

Constraints:

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5

Solution

This is a classic singly linked list problem and a very popular one in coding interviews, especially at the mid and entry levels. It requires you to have a good understanding of linked lists and basic pointer manipulation.

We will be using Floyd's Cycle Detection algorithm (also known as Tortoise and Hare Algorithm), a widely used technique for detecting cycles in linked list. The idea behind this algorithm is that, if we make use of two pointers: slow, fast and traverse through the list by moving the fast pointer at twice the speed of slow pointer, if a cycle exists, these two pointers are guaranteed to eventually meet at some point within that cycle.

Why this approach works?

This approach works because of the varying speeds of slow and fast pointers. Since one pointer moves slower than the other, once both of them enter the loop, the fast pointer at some point must overtake the slow pointer and that's when they meet.

This approach though conceptually simple and straight forward, is remarkably efficient both in terms of time and space complexity. Let's explore in detail how this works.

Algorithm

Below is a detailed explanation for the working of the algorithm:

Initialization:
1. Initialize two pointers: slow, fast.
2. Initially both slow and fast point to the head node.
Linked list traversal:
1. Traverse through the linked using slow and fast pointers.
2. In each iteration,
  1. Move slow pointer one step at a time (one node at a time).
  2. Move the fast pointer two steps at a time.
Cycle Detection:
1. If at any point during the traversal if slow pointer becomes equal to fast pointer, it means we have found a cycle, so return true as result.
2. If the loop exits without the pointers meeting, the list has no cycle. So, return false.

Simulation

Below diagram show a step-by-step simulation for the working of the algorithm:

Want to master coding? Looking to upskill and crack interviews? We suggest you check out

these specially designed courses:

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Complexity Analysis

Time Complexity

If there is no cycle:

If n is the number of nodes in the given linked list, if there is no cycle, the fast pointer takes n/2 iterations to reach the end of the list. Therefore the time complexity is O(n).

If there is a cycle:

Let's analyze this case in a bit more detail. n is the total number of nodes in the linked list. Let us assume that the cycle starts after m nodes and let k be the length of the cycle. fast pointer moves at twice the speed of slow pointer and if there is a cycle, slow and fast meet within the cycle.

The number of iterations required for them to meet is proportional to length of the cycle k. We know for sure that k <= n. Hence, the time complexity, though it might take a few more iterations compared to linked lists not having a cycle, it is still O(n).

Thus in general, the total time complexity is O(n).

Space Complexity

We only use two extra variables slow and fast, both of which use a constant extra space. Apart from this we do not use any extra space.

Hence the overall space complexity is O(1).

We hope this article has provided valuable insights. Thank you for taking the time to read it. If you have any questions or comments, please don't hesitate to share them below. We're always eager to engage with our readers and answer any inquiries you may have.

To stay updated on the latest articles and receive exclusive content, consider subscribing to our website and Youtube channel. Your support fuels our passion for creating informative and engaging content.

Special Offer: For a limited time, enjoy a 100% discount on the Code Recipe Membership Plan. Sign up now for free access to exclusive premium content. Don't miss out on this incredible opportunity! - Join now