Thank you for your great detailed solutions.
For Approach #3 it could get little improvement with just flipping dp and dp2 without new dp2 many times in loop.

Runtime: 40 ms beats 99.86 % of python3 submissions.
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
prev_node = None
curr_node = head
while curr_node:
next_node = curr_node.next # Remember next node
curr_node.next = prev_node # REVERSE! None, first time round.
prev_node = curr_node # Used in the next iteration.
curr_node = next_node # Move to next node.
head = prev_node
return head

I believe my Python solution is a bit more readable. It's more clear in my mind, if I just think of each iteration of the loop as a toggle between odd and even.

def oddEvenList(self, head):
odds = ListNode(0)
evens = ListNode(0)
oddsHead = odds
evensHead = evens
isOdd = True
while head:
if isOdd:
odds.next = head
odds = odds.next
else:
evens.next = head
evens = evens.next
isOdd = not isOdd
head = head.next
evens.next = None
odds.next = evensHead.next
return oddsHead.next

Rely to last comment @zhangyan985211 :
Think about a ascending array such as [1, 2, 3, 4....... 15000]. It could cause the worst time cost which is O(n^2).

@happyzone8 I guess the point is, for piv in the range of [start, start + len - 1], when piv == start + len - 1 it's certainly not to yield the minimum minres value that we look for. So we simply skip this possibility.
Otherwise we have to properly handle the case @jiadaizhao mentioned.

If wall width >> wall height, the approach #3 is not optimal. We do not need a HashMap with all gap positions. We just need a Heap with the closest gap locations. Then, the space complexity is O(height).

Kind of similar to #2, but without extra space usage and less iterations. But still running one unnecessary time on right side of max. So not as good as #4. But it might be more cache and branch prediction friendly friendly? Not sure.

Complexity:
Time = O(N) - worst 2N, best N, average 1.5N
Space = O(1)

class Solution {
public:
int trap(const std::vector<int>& heights) const {
int water = 0;
int water_at_max = 0;
int max_h = 0;
auto max_idx = 0u;
auto counter = 0u;
for (auto h : heights)
{
if (max_h <= h)
{
max_h = h;
max_idx = counter;
water_at_max = water;
}
water += max_h - h;
++counter;
}
water = 0;
max_h = 0;
for (auto itr = heights.rbegin(); itr != heights.rend() - max_idx; ++itr)
{
if (max_h <= *itr)
max_h = *itr;
water += max_h - *itr;
}
return water_at_max + water;
}
};