# Linked list Has Loop

Linked List with a Loop: A linked list with a loop (or a circular linked list) is a type of linked list where the last node of the list points back to one of the previous nodes, creating a loop or cycle in the list structure.

To represent a linked list with a loop, we use the ListNode class, which consists of a value and a next pointer. The next pointer points to the next node in the list. In the case of a circular linked list, the next pointer of the last node points back to one of the previous nodes in the list, creating a loop.

Solving LeetCode Problem - "Linked List Cycle": The problem we'll solve is called "Linked List Cycle," where we need to determine if a given linked list contains a cycle.

Here's the complete code with detailed comments:

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head):
"""
Checks if the given linked list contains a cycle.
"""
if not head or not head.next:
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
# Example usage
# Create a linked list with a cycle
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node2 # Creating a cycle
# Check if the linked list contains a cycle
has_cycle_result = has_cycle(head)
print("Linked List Contains Cycle:", has_cycle_result) # Output: True
```

Explanation:

- We define the ListNode class to represent a node in the linked list. Each node has a value and a next pointer that points to the next node in the list.
- The
`has_cycle`

function takes the head of the linked list as input and checks if the list contains a cycle. If there is a cycle, it returns True; otherwise, it returns False. - In the
`has_cycle`

function, we use the slow and fast pointer approach to detect a cycle. We initialize two pointers, slow and fast, both pointing to the head node. - We iterate through the linked list with the slow and fast pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
- If there is a cycle in the linked list, the fast pointer will eventually catch up with the slow pointer. In this case, we return True.
- If there is no cycle and the fast pointer reaches the end of the linked list (i.e., it becomes None or the next pointer of the fast pointer becomes None), we return False.

Time and Space Complexity Analysis:

- The time complexity of detecting a cycle in a linked list using the slow and fast pointer approach is O(n), where n is the number of nodes in the linked list. We traverse the linked list once.
- The space complexity is O(1) because we only use two pointers,
`slow`

and`fast`

, to detect the cycle. We don't use any additional data structures that scale with the input size.

The problem we'll solve is called "Linked List Cycle II" from LeetCode. Given a linked list, we need to return the node where the cycle begins if there is a cycle, or return null if there is no cycle.

Here's the complete code with detailed comments:

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detect_cycle(head):
"""
Returns the node where the cycle begins in the linked list,
or None if there is no cycle.
"""
if not head or not head.next:
return None
# Step 1: Check if a cycle exists
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
# No cycle found
return None
# Step 2: Find the node where the cycle begins
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
# Example usage
# Create a linked list with a cycle
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node3 # Creating a cycle
# Find the node where the cycle begins
cycle_node = detect_cycle(head)
if cycle_node:
print("Cycle Begins at Node with Value:", cycle_node.val) # Output: 3
else:
print("No Cycle Found")
```

Explanation:

- We define the ListNode class to represent a node in the linked list. Each node has a value and a next pointer that points to the next node in the list.
- The
`detect_cycle`

function takes the head of the linked list as input and returns the node where the cycle begins, or None if there is no cycle. - In the
`detect_cycle`

function, we use the slow and fast pointer approach to detect a cycle. We initialize two pointers, slow and fast, both pointing to the head node. - We iterate through the linked list with the slow and fast pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
- If there is a cycle in the linked list, the fast pointer will eventually catch up with the slow pointer. This indicates the presence of a cycle.
- After detecting the cycle, we reset the slow pointer to the head node and move both the slow and fast pointers one step at a time. The point at which they meet again is the node where the cycle begins.
- Finally, we return the node where the cycle begins or None if no cycle is found.

Time and Space Complexity Analysis:

- The time complexity of detecting the cycle and finding the node where the cycle begins is O(n), where n is the number of nodes in the linked list. We traverse the linked list at most twice.
- The space complexity is O(1) because we only use two pointers,
`slow`

and`fast`

, to detect the cycle and find the cycle's starting node. We don't use any additional data structures that scale with the input size.