Q141 Linked List Cycle

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

Follow up:
Can you solve it without using extra space?

解题思路：

首先，考虑了一种时间复杂度 O(n)，空间复杂度也为 O(n) 的方法。即用字典的键值保存已经出现过的地址。如果以后再出现该地址（dic.get[add]
为 True），则说明存在环。否则，不会有环。见Python实现1。

如果不使用额外的空间，即时间复杂度为 O(1)，没有想到方法。看到网上大神的思路，果然又是一道有技巧的题目。

如果有环，肯定从头到尾遍历链表是无法结束的，如图所示：

方法：定义两个指针，一个指针每次只走一步，另一个指针一次只走两步。如果有环，两个指针总会在某处相遇。如上图所示，如果两个指针都从1号结点出发，最后会在6号结点相遇。

网上也有证明的方法，这里略去。明白了这个技巧，则可以很容易实现，而且不会引入额外的空间，但是速度会比实现1慢一些。见Python实现2。

Python实现1：

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

# 方法1，空间复杂度 O(n)
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        add = {}
        cur = head
        while cur != None:
            if not add.get(cur):   # 判断键值是否存在的正确方法
                add[cur] = True
            else:
                return True  # 有环
            cur = cur.next
        return False  # 没有环

Python实现2：

# 方法2，空间复杂度 O(1)
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None:
            return False   # 没有环
        oneStep = twoStep = head
        while twoStep.next != None and twoStep.next.next != None:
            oneStep = oneStep.next  # 一次走一步
            twoStep = twoStep.next.next   # 一次走两步
            if oneStep == twoStep:  # 有环
                return True
        return False  # 没有环