This is what I wrote in the comments, formulated as an answer.

If $\hat{\beta}_j=0$, then $\hat{\alpha}_j\neq 0$ otherwise the matrix wouldn't be invertible. So you can swap column $j$ with column $n+j$ to make sure $\hat{\beta}_j \neq 0$ (and you need to swap $x_j$ and $x_{n+j}$ conformably to get an equivalent system). You can do this for all $j=1,2,\dots,n$, hence ensuring that $\hat{B}$ is nonsingular.

Then you can solve the system using the Schur complement of $\hat{B}$.

The cost of this direct algorithm is essentially that of forming the Schur complement ($2n^3$ flops) plus that of solving the linear system with it ($\frac23 n^3$ flops).

This is what I wrote in the comments, formulated as an answer.

If $\hat{\beta}_j=0$, then $\hat{\alpha}_j\neq 0$ otherwise the matrix wouldn't be invertible. So you can swap column $j$ with column $n+j$ to make sure $\hat{\beta}_j \neq 0$ (or better, as @wim suggests in the comments, $|\hat{\beta}_j| \geq |\hat{\alpha}_j|$) (and you need to swap $x_j$ and $x_{n+j}$ conformably to get an equivalent system). You can do this for all $j=1,2,\dots,n$, hence ensuring that $\hat{B}$ is nonsingular.

Then you can solve the system using the Schur complement of $\hat{B}$.

The cost of this direct algorithm is essentially that of forming the Schur complement ($O(n^2)$ flops, since two matrices are diagonal, as correctly noted by @wim) plus that of solving the linear system with it ($\frac23 n^3$ flops).