First ensure that you have installed mysql server fully:

apt-get install mysql-server-5.5 mysql-server

If you had installed only the former, you get the following error while starting mysql:

~# mysql -u root -p
Enter password:
ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/var/run/mysqld/mysqld.sock' (2)

Now, kill all mysql processes:

killall mysqld

Now run mysql in safe mode:

/usr/bin/mysqld_safe --skip-grant-tables &

Now you can enter mysql root without password:

# mysql --user=root
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.5.35-0+wheezy1 (Debian)

Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.

Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.


Now reset the password:

mysql> use mysql;
mysql> update user set Password=PASSWORD('newpasswordmine') WHERE User='root';
mysql> flush privileges;
mysql> exit

Now you can login to mysql and check:

service mysql restart

mysql -u root -p
Enter password: