141 linked list cycle
141. Linked List Cycle
题目:
https://leetcode.com/problems/linked-list-cycle/
难度:
Easy
想法一：
直接超时
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head == None: return False
lst = []
cur = head
while cur:
if cur in lst:
return True
lst.append(cur)
cur = cur.next
return False
想法二：相当用boolean array记录某个点是否被访问过，时间，空间复杂度都是O（n）
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head == None: return False
dictx = {}
cur = head
while cur:
if cur in dictx:
return True
dictx[cur] = 1
cur = cur.next
return False
结果这种方法的run time还比较快
查了一下，有解答说可以有空间复杂度O（1），时间复杂度O（n）。两个指针，一个快一个慢，快的每次走两步，慢的每次走一步，如果有环，最终会在某处相遇。这也是一个算法。这种快慢指针配合已经不是第一次遇到了，比如找linklist中间的node。
但是并没有觉得这样的算法是O(n)， worst case time complexity is O(N+K), which is O(n).
python
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
java
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null){
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && slow != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (slow == fast){
return true;
}
}
return false;
}
}
