I once had this problem and solved it by installing mysql-server, so make sure that you have installed the mysql-server, not the mysql-client or something else.
That error means the file /var/run/mysqld/mysqld.sock doesn’t exists, if you didn’t install mysql-server, then the file would not exist. So in that case, install it with
sudo apt-get install mysql-server
But if the mysql-server is already installed and is running, then you need to check the config files.
The config files are:
/etc/my.cnf
/etc/mysql/my.cnf
/var/lib/mysql/my.cnf
In /etc/my.cnf, the socket file config may be /tmp/mysql.sock and in /etc/mysql/my.cnf the socket file config may be /var/run/mysqld/mysqld.sock. So, remove or rename /etc/mysql/my.cnf, let mysql use /etc/my.cnf, then the problem may solved.