141. Linked List Cycle

[chengchengxu15]

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

[chengchengxu15]

Solution 1: Hash table:

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        dict = {}
        while head != None and head.next != None:
            if head in dict:
                return True
            else:
                dict[head] =1
                head = head.next
        return False

time complexity: O(n) space complexity: O(n)

[chengchengxu15]

Solution 2: 2 pointers 龟兔赛跑 有点东西啊 官方答案：https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/ time complexity: O(n) 当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。

当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 n+[n/2] 轮。

space complexity: O(1)

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        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