Description:
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.
Examples:
Example 1:
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).
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Solution in Python:
To determine if a linked list has a cycle, we can use Floyd’s Cycle-Finding Algorithm, also known as the Tortoise and Hare Algorithm. This algorithm uses two pointers moving at different speeds to detect a cycle.
Here’s how the algorithm works:
- Initialization: Start with two pointers,
slowandfast. Initially, both pointers point to the head of the linked list. - Movement: Move the
slowpointer one step at a time and thefastpointer two steps at a time. - Cycle Detection: If there is a cycle, the
fastpointer will eventually meet theslowpointer. If there is no cycle, thefastpointer will reach the end of the list (None).
Python
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# Initialize the slow and fast pointers to the head of the list
slow = head
fast = head
# Traverse the list with the two pointers
while fast and fast.next:
# Move the slow pointer by one step
slow = slow.next
# Move the fast pointer by two steps
fast = fast.next.next
# Check if the slow and fast pointers meet
if slow == fast:
return True
# If the fast pointer reaches the end of the list, there is no cycle
return FalseSolution in Javascript:
JavaScript
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
// Initialize the slow and fast pointers to the head of the list
let slow = head;
let fast = head;
// Traverse the list with the two pointers
while (fast !== null && fast.next !== null) {
// Move the slow pointer by one step
slow = slow.next;
// Move the fast pointer by two steps
fast = fast.next.next;
// Check if the slow and fast pointers meet
if (slow === fast) {
return true;
}
}
// If the fast pointer reaches the end of the list, there is no cycle
return false;
};Solution in Java:
Java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
// Initialize the slow and fast pointers to the head of the list
ListNode slow = head;
ListNode fast = head;
// Traverse the list with the two pointers
while (fast != null && fast.next != null) {
// Move the slow pointer by one step
slow = slow.next;
// Move the fast pointer by two steps
fast = fast.next.next;
// Check if the slow and fast pointers meet
if (slow == fast) {
return true;
}
}
// If the fast pointer reaches the end of the list, there is no cycle
return false;
}
}Solution in C#:
C#
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public bool HasCycle(ListNode head) {
// Initialize the slow and fast pointers to the head of the list
ListNode slow = head;
ListNode fast = head;
// Traverse the list with the two pointers
while (fast != null && fast.next != null) {
// Move the slow pointer by one step
slow = slow.next;
// Move the fast pointer by two steps
fast = fast.next.next;
// Check if the slow and fast pointers meet
if (slow == fast) {
return true;
}
}
// If the fast pointer reaches the end of the list, there is no cycle
return false;
}
}