Consider whether the last element is odd or even and then put it at the appropriate location based on this and recurse.