Reverse a Singly Linked List In-Place

Context: You are given the head of a standard singly linked list (each node has value and next). Implement and explain robust reversal routines that work for empty lists, single-node lists, very long lists (up to 10^6 nodes), and lists that may contain a cycle.

Requirements

1. Implement two versions:
   • Iterative reversal with O(1) extra space.
   • Recursive reversal. Explain how you avoid stack overflow for up to 10^6 nodes using either tail-recursion elimination (where available) or chunked recursion.
2. Edge cases:
   • Empty list.
   • Single node.
   • Very long list (≈ 10^6 nodes).
3. Cycles:
   • Detect a cycle using Floyd’s tortoise–hare algorithm.
   • Choose one policy:
     • Preserve the cycle orientation while reversing the linear segment, or
     • Break the cycle before reversing.
   • Justify your choice and implement accordingly.
4. Include:
   • Time and space complexity analysis.
   • A loop invariant to argue correctness of the iterative solution.
   • A minimal but sufficient test set.