题目描述：

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

Follow up:

Can you solve it without using extra space?

题目大意：

给定一个链表，判断其中是否有环。

进一步思考：

你可以在不使用额外空间的条件下完成本题吗？

解题思路：

使用“快慢指针”法即可

fast指针每次向前运动两个节点，slow指针每次向前运动一个节点

如果fast和slow在链表的某处相遇，则说明链表中有环

Python代码（快慢指针）：

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

class Solution:
    # @param head, a ListNode
    # @return a boolean
    def hasCycle(self, head):
        if not head:
            return False
        slow = fast = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

另一种解法是使用set记录每次访问过的节点，若某节点被二次访问，则说明链表中有环。

Python代码（使用set）：

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

class Solution:
    # @param head, a ListNode
    # @return a boolean
    def hasCycle(self, head):
        nodeSet = set()
        p = head
        while p:
            if p in nodeSet:
                return True
            nodeSet.add(p)
            p = p.next
        return False

 

本文链接：http://bookshadow.com/weblog/2015/06/26/leetcode-linked-list-cycle/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码