# Solution For Linked List Cycle

The Linked List Cycle problem on LeetCode is a classic problem that involves identifying whether a linked list has a cycle or not. In this problem, you are given a linked list and are to determine whether it has a cycle or not.

A linked list consists of a series of nodes that are connected to each other. Each node contains a value and a reference to the next node in the list. If the last node in the list has a reference to null, then the linked list is considered to be terminated. However, if any node in the list references an earlier node, then the linked list contains a cycle.

To solve this problem, we need to use the Floyd’s cycle-finding algorithm, also known as the “turtle and hare” algorithm. This algorithm involves traversing the linked list with two pointers, one moving faster than the other. If the linked list contains a cycle, then the faster pointer will eventually catch up to the slower pointer, indicating that a cycle has been found.

Here’s the detailed solution:

- We start by initializing two pointers, slow and fast, to point to the head of the linked list.
- We then iterate through the linked list. During each iteration, the slow pointer moves one step forward while the fast pointer moves two steps forward.
- We check at each step whether the fast pointer has reached the end of the list or not. If it has, then the linked list does not contain a cycle. Otherwise, we continue iterating through the list.
- If the fast pointer catches up to the slow pointer, then a cycle has been found, and we return true. Otherwise, we return false.

Here’s the Python code that implements this approach:

“`

class Solution:

def hasCycle(self, head: ListNode) -> bool:

if not head:

return False

```
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
```

“`

In the code above, we first check whether the head of the linked list is None. If it is, then we know for sure that the linked list does not contain a cycle (since there are no nodes to iterate through).

We then initialize the slow and fast pointers to point to the head of the linked list and its next node, respectively. We then iterate through the linked list using a while loop. During each iteration, we check whether the fast pointer has reached the end of the list (i.e., it is pointing to None), in which case we know for sure that the list does not contain a cycle. Otherwise, we move the slow pointer one step forward and the fast pointer two steps forward.

Finally, if the fast pointer ever catches up to the slow pointer, then we know that a cycle has been found, and we return True. Otherwise, we return False.

This solution has a time complexity of O(n), where n is the number of nodes in the linked list. It also has a space complexity of O(1), since we are only using two pointers to traverse the linked list.

## Step by Step Implementation For Linked List Cycle

/** * 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) { // if head is null, there is no cycle if (head == null) { return false; } // if head.next is null, there is no cycle if (head.next == null) { return false; } // create two pointers, slow and fast // slow moves one node at a time // fast moves two nodes at a time ListNode slow = head; ListNode fast = head.next; // while fast is not null and fast.next is not null // keep iterating while (fast != null && fast.next != null) { // if slow == fast, there is a cycle if (slow == fast) { return true; } // move slow one node slow = slow.next; // move fast two nodes fast = fast.next.next; } // if we reach here, that means there is no cycle return false; } }

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ # check for empty list if not head: return False # if only one element in list, can't be a cycle if not head.next: return False # use Floyd's cycle detection algorithm # two pointers, one moves one node at a time, # the other moves two nodes at a time # if there is a cycle, the two pointers will eventually meet slow = head fast = head.next while slow != fast: # check for end of list - no cycle if not fast or not fast.next: return False slow = slow.next fast = fast.next.next return True

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function(head) { // if head is null, return false if (!head) { return false; } // define two pointers, slow and fast let slow = head; let fast = head; // while loop will continue until slow === fast (which means they met in the cycle) // or fast.next === null (which means there is no cycle) while (slow !== fast || fast.next !== null) { // if fast.next is null, that means there is no cycle if (fast.next === null) { return false; } // move slow pointer one node at a time slow = slow.next; // move fast pointer two nodes at a time fast = fast.next.next; } // if the while loop exits, that means there is a cycle return true; };

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { if (!head || !head->next) return false; ListNode *slow = head, *fast = head->next; while (slow != fast) { if (!fast || !fast->next) return false; slow = slow->next; fast = fast->next->next; } return true; } };

/** * 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) { // if head is null or only has one node, then it can't have a cycle if (head == null || head.next == null) { return false; } // use two pointers, slow and fast // slow moves one node at a time, while fast moves two nodes at a time // if there is a cycle, slow and fast will eventually meet ListNode slow = head; ListNode fast = head.next; while (slow != fast) { // if fast reaches the end of the list, then there is no cycle if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } }