Linked List Cycle

EasyLinked Listlinked-list-cycle-detection

Given the head of a singly linked list, return true if there is a cycle in the linked list, otherwise return false.

There is a cycle in a linked list if at least one node in the list can be visited again by following the next pointer.

Constraints:

  • The number of nodes in the list is in the range [1, 1000].
  • Node values are in the range [-1000, 1000].
  • The index parameter (not passed to the function) determines the index where the cycle begins, if it exists. If index = -1, then no cycle exists.

Example 1:

Input: head = [1, 2, 3, 4], index = 1 Output: true

Example 2:

Input: head = [1], index = -1 Output: false

Recommended time and space complexity

You should aim for a solution with O(n) time complexity and O(1) space complexity for the optimal approach.


Hint 1

A brute force approach would be to use a hash table to store visited nodes. This would be an O(n) time and O(n) space solution. Can you think of a more efficient approach?


Hint 2

Can you use two pointers moving at different speeds to detect a cycle?


Hint 3

Use the "tortoise and hare" method (Floyd's algorithm) to detect a cycle without using additional memory.

This problem tests the ability to efficiently determine whether a cycle exists in a singly linked list. It helps develop skills in working with pointers and improves understanding of time and space complexity of algorithms. Solving this problem promotes logical thinking and the ability to optimize code for working with large amounts of data.
solution.js · saved

Input

head = [1, 2, 3, 4] index = 1

Expected Output

true