This is very similar to my own first solution. The running time is a little embarrassing though compared with the optimal solution. Posting my code here.

public class Solution {
public int maxDistance(List<List<Integer>> arrays) {
List<List<Integer>> res = new ArrayList<>();
int n = arrays.size();
int minMin = Integer.MAX_VALUE, maxMax = Integer.MIN_VALUE;
List<Integer> lsMin = new ArrayList<>();
List<Integer> lsMax = new ArrayList<>();
for (List<Integer> ls : arrays) {
int index = arrays.indexOf(ls);
int thisMin = ls.get(0), thisMax = ls.get(ls.size() - 1);
if (thisMin < minMin) {
minMin = thisMin;
lsMin.clear();
lsMin.add(index);
} else if (thisMin == minMin) {
lsMin.add(index);
}
if (thisMax > maxMax) {
maxMax = thisMax;
lsMax.clear();
lsMax.add(index);
} else if (thisMax == maxMax) {
lsMax.add(index);
}
}
int accum = 0;
for (int i : lsMin) accum ^= i;
for (int i : lsMax) accum ^= i;
if (accum != 0 || (accum == 0 && lsMin.size() > 1)) return maxMax - minMin;
//minMin and maxMax in same list: either one of them will be in the maximum distance
int avoidIndex = lsMin.get(0);
int secondMin = Integer.MAX_VALUE, secondMax = Integer.MIN_VALUE;
for (int i = 0; i < arrays.size(); i++) {
if (i == avoidIndex) continue;
List<Integer> ls = arrays.get(i);
int thisMin = ls.get(0), thisMax = ls.get(ls.size() - 1);
if (thisMin < secondMin) secondMin = thisMin;
if (thisMax > secondMax) secondMax = thisMax;
}
return Math.max(Math.abs(maxMax - secondMin), Math.abs(minMin - secondMax));
}
}

If it is at all possible for the global min and global max to not occur in the same list(considering duplicates), then the max distance is just abs(max-min).

But if not, we find the secondMin and the secondMax, and the max distance must involve at least one of min and max. This solution has bad running time, just posting here for fun.