Show that two matrices with the same eigenvalues are similar

The idea in your approach almost works. But you cannot assume that $A$ and $B$ have the same eigenvectors! So you will have $$ Ax_j=\lambda_jx_j,\ \ \ By_j=\lambda_jy_j. $$ As $\lambda_1,\ldots,\lambda_p$ are distinct, $x_1,\ldots,x_p$ and $y_1,\ldots,y_p$ are each linearly independent, so they are bases. Let $P$ be the change of basis $y\to x$, i.e. $P$ is the matrix such that $Py_j=x_j$, $j=1,\ldots,n$. It is clearly nonsingular: if $P(c_1y_1+\cdots+c_py_p)=0$, then $$ 0=c_1P(y_1)+\cdots+c_pP(y_p)=c_1x_1+\cdots+c_px_p, $$ so $c_1=\cdots=c_p=0$. Now, for each $j$, $$ PBy_j=\lambda_j Py_j=\lambda_jx_j=Ax_j=APy_j. $$ As the $y$ are a basis, we get that $PB=AP$, i.e. $PBP^{-1}=A$.

Another way to proceed is to note that there is an invertible $p \times p$ matrix $S$ such that $S^{-1}AS = {\rm diag}(\lambda_{1},\ldots,\lambda_{p})$ and there is an invertible $p \times p$ matrix $T$ such that $T^{-1}BT = {\rm diag}(\lambda_{1},\ldots,\lambda_{p}).$ Then $TS^{-1}AST^{-1} = B,$ and we can take $P = (ST^{-1}).$

Be careful! If A and B are $n\times n$ matrices having the same p distinct eigenvalues where $p<n$ this argument doesn't work. Because in this case the base change matrix P would be a $p\times p$ matrix and we cannot multiply an $n \times n$ matrix with a $p\times p$ matrix.