Solve linked list, grid BFS, and median queries

You are given three separate algorithmic tasks.

1) Reorder a linked list by odd/even positions

Given the head of a singly linked list, reorder the nodes so that all nodes at odd indices come first, followed by all nodes at even indices (1-indexed positions). Within the odd group and within the even group, preserve the original relative order.

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

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

2) Shortest distance between any two islands (grid variant)

You are given an m x n grid of 0/1 where 1 indicates land and 0 indicates water. An island is a connected component of 1s using 4-directional adjacency.

You may convert water cells to land; the “distance” between two islands is the minimum number of 0 cells that must be converted to create a 4-directional land path between them.

Return the minimum distance over all pairs of distinct islands.

• Input: grid[m][n] of 0/1
• Output: integer minimum number of flips
• Assumptions/constraints:
  • m, n up to ~ 10^3 (design an efficient approach)
  • There are at least 2 islands

3) Find the median using a rank-count oracle

There are N unknown integers (you do not get direct access to the array). You are given:

• The total count N .
• An oracle function countLessGreater(x) that returns two integers:
  • L(x) : how many numbers are strictly less than x
  • G(x) : how many numbers are 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 are greater than m .
• If N is even, return the lower median (the N/2 -th smallest; 1-indexed).

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