Access denied for user 'root'@'localhost' (using password: NO) on 'service mysql start'
I had similar problem.

https://stackoverflow.com/questions/38098505/mysql-works-with-sudo-but-without-not-ubuntu-16-04-mysql-5-7-12-0ubuntu1-1

And solved id following by:

https://askubuntu.com/questions/766334/cant-login-as-mysql-user-root-from-normal-user-account-in-ubuntu-16-04

sudo mysql -u root
DROP USER 'root'@'localhost';
CREATE USER 'root'@'%' IDENTIFIED BY '';
GRANT ALL PRIVILEGES ON *.* TO 'root'@'%';
FLUSH PRIVILEGES;