Skip to content

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


回到顶部