8. Linked list problems

public class Node(int value) { public int Value = value; public Node? Next; }

// Reverse a linked list — iterative O(n), O(1)
static Node? Reverse(Node? head)
{
    Node? prev = null;
    while (head is not null)
    {
        var next = head.Next;
        head.Next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

// Detect a cycle — Floyd's slow/fast pointers
static bool HasCycle(Node? head)
{
    Node? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next; fast = fast.Next.Next;
        if (slow == fast) return true;
    }
    return false;
}

// Middle node — slow moves 1, fast moves 2
static Node? Middle(Node? head)
{
    Node? slow = head, fast = head;
    while (fast?.Next is not null) { slow = slow!.Next; fast = fast.Next.Next; }
    return slow;
}