1
2# Given a linked list, determine if it has a cycle in it.
3#
4# Follow up:
5# Can you solve it without using extra space?
6
7# Definition for singly-linked list.
8# class ListNode(object):
9#     def __init__(self, x):
10#         self.val = x
11#         self.next = None
12
13
14class Solution(object):
15    def hasCycle(self, head):
16        """
17        :type head: ListNode
18        :rtype: bool
19        """
20        if head is None:
21            return False
22        slow, faster = head, head.next
23        while faster is not None:
24            slow = slow.next
25            if faster.next is not None:
26                faster = faster.next.next
27            else:
28                return False
29            if slow is faster:
30                return True
31        return False
32
33class ListNode(object):
34    def __init__(self, x):
35        self.val = x
36        self.next = None
37
38
39head = ListNode(1)
40two = ListNode(2)
41two.next = head
42head.next = two
43
44print(Solution().hasCycle(head))
45