## Problem Statement

Given a linked list. Determine if the linked list has a cycle in it.

A linked list contains a cycle if it consists of a node that can be reached again by continuously following the **next** pointer.

**Examples:**

**Input: **

**Output: **True**Explanation:**

The linked list consists of a loop, where the last node connects to the second node.

**Input: **

**Output:** True

## HashSet Approach

The simplest approach to solve this problem is to check whether a node in the linked list has been visited before. To perform this operation, a hashmap can be used.

**Algorithm**

- Initialise a hashmap.
- Traverse the linked list till the
**head**pointer isn’t**NULL:**- If the current node is already present in the hashset, it ensures that the linked list contains a loop. Hence, terminate and return
**True**. - Else, continue traversing and continue inserting the node into the hashset.

- If the current node is already present in the hashset, it ensures that the linked list contains a loop. Hence, terminate and return
- Return
**False**if it doesn’t satisfy the above conditions.

### C++ Implementation

bool hasCycle(Node* head) { set<Node*> mp; while (head != null) { if (mp.find(head) != mp.end()) { return true; } mp[head]++; head = head->next; } return false; }

### Java Implementation

public boolean hasCycle(ListNode head) { Set<ListNode> mp = new HashSet<>(); while (head != null) { if (mp.contains(head)) { return true; } mp.add(head); head = head.next; } return false; }

### Python Implementation

def hasCycle(head): mp = set() while head is not None: if head in mp: return True mp.add(head) head = head.next return False

**Time Complexity:** O(N) where N is the number of nodes of the linked list**.****Space Complexity:** O(N), as HashSet is used

## Floyd’s Cycle Detection Algorithm

This approach uses a two-pointer – a **fast pointer **and a **slow pointer** to determine if there exists a cycle in the loop. The **slow pointer** moves one node ahead at a time, while the **fast pointer **moves two nodes ahead at a time.

If a loop exists in the linked list, the **fast **and **slow** pointers are bound to meet at some point.

**Algorithm: **

- Initialise two pointers,
**fast**and**slow**to the**head**of the linked list. - Traverse through the linked list until the
**fast**pointer doesn’t reach the end of the linked list. - If the
**fast**pointer reaches the end, it means that the linked list doesn’t contain any cycle. Hence, return**False.** - Else, move the
**slow**pointer by one node i.e.**slow = slow -> next**and**fast**pointer by two nodes i.e.**fast = fast -> next -> next**. - At any point, if the
**fast**and the**slow**pointers point to the same node, return**True**as a loop has been detected.

### C++ Code for Two Pointer Approach

bool hasCycle(ListNode *head) { if (head == NULL) return false; ListNode *slow = head; ListNode* *fast = head; while (slow != fast) { if (fast == Null || fast->next == NULL) { return false; } slow = slow->next; fast = fast->next->next; } return true; }

### Java Code for Two Pointer Approach

public boolean hasCycle(ListNode head) { if (head == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; }

### Python Code for Two Pointer Approach

def hasCycle(self, head: ListNode) -> bool: if head is None: return False slow = head fast = head.next while slow != fast: if fast is None or fast.next is None: return False slow = slow.next fast = fast.next.next return True

**Time Complexity:** O(N), where N is the number of nodes of the linked list**.****Space Complexity:** O(1), as a map is used.

## Practice Question

## Frequently Asked Questions

**How do you detect a loop in a linked list?**A loop can be detected efficiently using the fast and slow pointer algorithm, where the fast pointer moves by two nodes and the slow pointer move by one node at a time.

**Will the fast and slow pointer always meet at some point if the list contains a cycle?**Yes, if the linked list contains a cycle, the fast and slow pointer will always meet at some point.