Time Complexity isn't O(N) in zigzag traversal solution

Here we are using ArrayList#add(index, value), which has time cost of O(N) and hence the mentioned solution have O(N^2) time complexity. Please correct!

Maybe a better solution to this problem would be to use Deque as it has the methods offerFirst and offerLast which are O(1) complexity.