141._linked_list_cycle.md

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;
    }
}