Algorithmic Tasks

You are presented with three independent algorithmic tasks.

Task 1: Reorder a Linked List by Odd/Even Positions

Given the head of a singly linked list, reorder the nodes such that all nodes at odd indices come first, followed by all nodes at even indices (1-indexed positions). Within both the odd and even groups, the original relative order of nodes must be preserved.

• Input: head of a singly linked list
• Output: The head of the reordered list
• Constraints: O(1) extra space (excluding recursion stack space), O(n) time complexity.

Example: 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 3 -> 5 -> 2 -> 4.

Task 2: Shortest Distance Between Any Two Islands (Grid Variant)

You are given an m x n grid composed of 0s and 1s, where 1 represents land and 0 represents water. An island is defined as a 4-directionally connected component of 1s.

You are allowed to convert water cells (0) to land cells (1). The "distance" between two islands is the minimum number of 0 cells that must be converted to create a 4-directional land path connecting them.

Your task is to return the minimum distance over all pairs of distinct islands.

• Input: grid[m][n] of 0/1
• Output: An integer representing the minimum number of flips
• Assumptions/Constraints:
  • m, n can be up to approximately 10^3. Design an efficient approach.
  • There are guaranteed to be at least two distinct islands in the grid.

Task 3: Find the Median Using a Rank-Count Oracle

There are N unknown integers, and you do not have direct access to the array containing them. You are provided with:

• The total count N of these integers.
• An oracle function countLessGreater(x) that, when called with an integer x, returns two integers:
  • L(x): The count of numbers strictly less than x.
  • G(x): The count of numbers strictly greater than x.

Using only calls to this oracle, find a median value.

• If N is odd, return the value m such that exactly (N-1)/2 numbers are less than m and (N-1)/2 numbers are greater than m.
• If N is even, return the lower median (defined as the N/2-th smallest value, using 1-indexed ranking).

State any additional assumptions you need (e.g., a known bounded integer range), and design an algorithm that minimizes the number of oracle queries.