 Solution

If $p$ and $q$ both interpolate the data and have degree at most $n$, the polynomial $r=p-q$ has the $n+1$ distinct roots $x_0,\dots ,x_n$. A nonzero polynomial of degree at most $n$ has at most $n$ roots: repeated use of the factor theorem would otherwise make a product of $n+1$ linear factors divide it. Hence $r=0$, proving the interpolating polynomial is unique.