141. Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/

solution

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None or head.next is None:
            return False

        slow = head
        fast = head.next
        while fast is not None and fast.next is not None:
            if slow == fast:
                return True

            slow = slow.next
            fast = fast.next.next

        return False

时间复杂度：O(n) 空间复杂度：O(1)

follow up

• SPFA 判断是否有负环

import collections
n, m = map(int, input().split())

g = collections.defaultdict(list)
st = [True for i in range(n+1)]
dist = [0 for i in range(n+1)]
cnt = [0 for i in range(n+1)]

for i in range(m):
    a, b, w = map(int, input().split())
    g[a].append([b, w])

def spfa():
    q = [i for i in range(n+1)]
    while len(q) != 0:
        a = q.pop()  ## 这里要注意 如果用pop(0) 会超时，这是因为 Python中 pop(0)复杂度O(n),pop()是O(1)
        st[a] = False
        for b, w in g[a]:
            if dist[b] > dist[a] + w:
                cnt[b] = cnt[a] + 1
                if cnt[b] >= n:
                    return True
                dist[b] = dist[a] + w
                if st[b] == False:
                    q.append(b)
    return False

print("Yes" if spfa() else "No")