---
tags: data_structure_python
---

# Linked List Cycle <img src="https://img.shields.io/badge/-easy-brightgreen">

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer ```pos``` which represents the position (0-indexed) in the linked list where tail connects to. If ```pos``` is ```-1```, then there is no cycle in the linked list.

<ins>**Example 1:**</ins>

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

<br>

<div style="text-align:center">
<img src="https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png" width=50%>
</div>

<ins>**Example 2:**</ins>

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

<br>

<div style="text-align:center">
<img src="https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png">
</div>

<ins>**Example 3:**</ins>

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

<br>

<div style="text-align:center">
<img src="https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png">
</div>

# Solution

### Solution 1: Version 1 (Draft)

#Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # O(n).
        pointer1 = head
        if pointer1 == None or pointer1.next == None or pointer1.next.next == None:
            return False    
        pointer2 = head.next.next
        while pointer1.next != None :
            if pointer1.val == pointer2.val:
                return True
            if pointer2.next == None or pointer2.next.next == None:
                return False
            pointer1 = pointer1.next
            pointer2 = pointer2.next.next         
        return False

### Solution 2: Version 2 (Clean)

#Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

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