LinkedList Cycle Detector

Function Name: hasCycle

Description

Write a function `hasCycle` in a language of your choice that takes a linked list as an input and returns a boolean indicating whether the linked list contains a cycle.

A linked list is said to contain a cycle if any node is visited more than once while traversing the list.

To solve this problem, you should detect if the linked list has a cycle without using extra space (e.g., an additional data structure like a hash table).

Assume that the linked list is a singly linked list provided with the next pointer.

Your function should be able to return false if the input is an empty list or a single-node list without a cycle, and true if a cycle is detected.

Requirements

• The function `hasCycle` should take a single parameter that represents the head of the linked list.
• The function should return a boolean value.
• Do not use external libraries or additional data structures.
• Minimize the space complexity of the function; strive for O(1) space.
• Consider edge cases like an empty list and lists with only one node.
• You must use Floyd's Cycle-Finding Algorithm (also known as the tortoise and hare algorithm).

Examples

If the linked list has the following nodes where the last node points back to the second node: 1 -> 2 -> 3 -> 4 -> 2 (cycle), `hasCycle(head)` should return true.If the linked list has the following nodes with no cycle: 1 -> 2 -> 3 -> 4, `hasCycle(head)` should return false.For an empty list, `hasCycle(head)` should return false.For a single-node list, `hasCycle(head)` should also return false.

Links