Detect cycles in lists and graphs

Given a singly linked list, determine whether it contains a cycle. Implement an O( 1)-space algorithm and explain the intuition and correctness. Follow-up: Generalize to a directed graph where each node may have multiple children. Given a starting node, determine whether a cycle exists reachable from it. Discuss how you'd handle disconnected graphs, very large graphs that may not fit in memory, and the time/space complexity trade-offs. Provide pseudocode or code for both parts.