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

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

思路

先尝试最直观的方法，将所有的节点都存起来，感觉上是比较麻烦。至少是O(n^2)的复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        nodes = []
        cur = head
        while (cur):
            nodes.append(cur)
            if (cur.next):
                if (cur.next in nodes):
                    return True
            cur = cur.next
        return False

利用哈希表对于这些节点进行存储，时间开销就会减少了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        nodes = {}
        cur = head
        while (cur):
            nodes[cur] = 1
            if (cur.next):
                if (nodes.has_key(cur.next)):
                    return True
            cur = cur.next
        return False

另外，利用快慢指针的方法也非常巧妙。快的指针每次前进两步，慢的指针每次前进一步。如果链表里面有一个环，快慢指针一定会相遇。