If there are equal coefficients for $x^{2n-t}$ and $x^t$ for all $0 \le t \lt n$ then we have $n+1$ unknown coefficients so $n+1$ points suffice. Of course that is still $O(n).$
For the quadratic case $y=ax^2+bx+a$ we have $y(i)=bi.$
For $y=ax^4+bx^3+cx^2+bx+a$ we have $y(-1)=2a+c$ and $y(0)=a.$
for $y=ax^6+bx^5+cx^4+dx^3+cx^2+bx+a$ it is enough to have $y$ at $i$ and at $\frac{\pm1+\sqrt{3}i}{2}$
This suggests a reduction from $n+1$ to $n$ points. This is not using the fact that the coefficients are integers.