题目描述:
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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
硅藻泥缺点 发布于 2015年6月29日 14:19 #
[路过这儿]
Reborn 发布于 2017年12月12日 10:49 #
Thanks for sharing!
Your solution is always clean and clear!
Love it