一天两道力扣（5）

class Solution(object): def canFinish(self, numCourses, prerequisites): indegrees = [0 for _ in range(numCourses)] adjacency = [[] for _ in range(numCourses)] queue = deque() for cur, pre in prerequisites: indegrees[cur] += 1 adjacency[pre].append(cur) for i in range(len(indegrees)): if not indegrees[i] : queue.append(i) while queue: pre = queue.popleft() numCourses -= 1 for cur in adjacency[pre]: indegrees[cur] -= 1 if not indegrees[cur]: queue.append(cur) return not numCourses

这段代码使用 ​​拓扑排序（Kahn算法）​​ 判断能否完成所有课程（判断有向无环图DAG是否存在环）。具体思路：

1. ​​初始化入度表（indegrees）和邻接表（adjacency）​​：统计每门课程的依赖数量（入度）及其后继课程。
2. ​​将入度为0的课程加入队列​​：这些课程没有先修要求，可直接学习。
3. ​​处理队列中的课程​​：每学完一门课程（numCourses -= 1），减少其后续课程的入度；若后续课程入度变为0，则加入队列。
4. ​​最终判断​​：若所有课程均被处理（numCourses == 0），说明无环，可以完成；否则存在环，无法完成。

​​核心思想​​：通过不断移除入度为0的节点，检测图中是否剩余未被处理的节点（即是否存在环）。

class Solution(object): def reverseList(self, head): cur, pre = head, None while cur: tmp = cur.next cur.next = pre pre = cur cur = tmp return pre