1. Stop mysql:
$ sudo service mysql stop

2. Step 2: Kill all running mysqld
$ sudo killall -9 mysqld

3. Step 3: Starting mysqld in Safe mode.
$ sudo mysqld_safe --skip-grant-tables --skip-networking &

4. Login as root
$ mysql -u root

5. Update the root user password with these mysql commands
mysql> UPDATE mysql.user SET authentication_string = PASSWORD('MyNewPassword') WHERE User = 'root' AND Host = 'localhost';
mysql> FLUSH PRIVILEGES;
mysql> quit

6. Make sure!: Kill all running mysqld
$ sudo killall -9 mysqld

7. Start mysql normally:
sudo service mysql start

Try to login using your new password:
8. mysql -u root -p