Solve linked list reversal and minima problems

You are given three independent coding tasks.

1) Reverse a singly linked list

Input: The head of a singly linked list.

Output: The head of the same list with nodes reversed.

Constraints / Notes:

• Aim for $O(n)$ time.
• Prefer $O(1)$ extra space (iterative), but you may also discuss a recursive approach.

2) Find the minimum number in a rotated matrix

Assume the matrix represents a rotated sorted sequence when read in row-major order:

• If you flatten the $m \times n$ matrix into an array in row-major order, that flattened array was originally sorted in strictly increasing order and then rotated (circularly shifted) by an unknown offset.

Input: An $m \times n$ integer matrix mat with m,n >= 1 satisfying the property above.

Output: The minimum value in the matrix.

Constraints / Notes:

• Target $O(\log(mn))$ time by using binary search over the implicit flattened array.

3) Find the minimum value in a linked list

Input: The head of a singly linked list of integers (not necessarily sorted).

Output: The minimum integer value contained in the list.

Constraints / Notes:

• $O(n)$ time, $O(1)$ extra space.
• Specify what to do if the list is empty (e.g., return null /raise an exception).