leetcode/double_pointer/has_cycle.py

from typing import Optional

import pytest

from utils import ListNode, arr_to_linklist

def hasCycle(head: Optional[ListNode]) -> bool:
    # if not head or not head.next:
    #     return False
    # p = q = head
    # while p.next or q.next:
    #     if q.next is None:
    #         p = p.next
    #         q = p.next
    #     elif p.next is None:
    #         return False
    #     elif q.next != p:
    #         q = q.next
    #     else:
    #         return True

    # 哈希表法
    # res = set()
    # while head:
    #     if head in res:
    #         return True
    #     res.add(head)
    #     head = head.next
    # return False

    # 快慢指针法
    if not head or not head.next:
        return False
    slow = head
    fast = head.next
    while fast != slow:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next

    return True




@pytest.mark.parametrize(
    "head, expect",
    [
        ([3,2,0,-4], True)
    ]
)

def test_cases(head, expect):
    assert hasCycle(arr_to_linklist(head)) == expect