Clean installation of mysql-server on Ubuntu (also happened to me on Debian), i can't connect with root and no password (even though on installation i set a blank password). This is not MariaDB, it's the proper 5.7 version installed via package repository after using the Mysql APT tool to set it up.

Here's the shit i had to do to make this work:

sudo emacs /lib/systemd/system/mysql.service

In this file, add --skip-grant-tables to the Exec command. After that run:

sudo systemctl daemon-reload
sudo service mysql restart

Now login into Mysql:

mysql -uroot

And run these commands to reset the root user's credentials:

use mysql;
update user set authentication_string=PASSWORD("") where User='root';
update user set plugin="mysql_native_password" where User='root';
flush privileges;
quit;

Now, just revert what you did to the startup script, don't forget to run systemctl reload and restart the service and logging in with root should work. 

I curse you, Oracle.