reset-root-password-ubuntu16.04.txt

What worked for me (Ubuntu 16.04, mysql 5.7):

Stop MySQL

sudo service mysql stop
Make MySQL service directory.

sudo mkdir /var/run/mysqld
Give MySQL user permission to write to the service directory.

sudo chown mysql: /var/run/mysqld
Start MySQL manually, without permission checks or networking.

sudo mysqld_safe --skip-grant-tables --skip-networking &
On another console, log in without a password.

mysql -uroot mysql
Then:

UPDATE mysql.user SET authentication_string=PASSWORD('YOURNEWPASSWORD'), plugin='mysql_native_password' WHERE User='root' AND Host='%';
EXIT;
Turn off MySQL.

sudo mysqladmin -S /var/run/mysqld/mysqld.sock shutdown
Start the MySQL service normally.

sudo service mysql start