Sfdwhf

Try doing a purge, then re-install.

sudo apt-get remove --purge mysql-*

sudo apt-get install mysql-server mysql-client

Update 04.09.2018:

If you have issues uninstalling/installing because MySQL process is live, you can try this first, then above:
sudo kill $(pgrep mysql)

A very simple solution which I (the linux noob) had to dig up... is to create the file.

nano /etc/mysql/my.cnf.fallback

and fill it with the default content from the mysql-common 5.7.11-0ubuntu6 package.

#

# The MySQL database server configuration file.

#

# You can copy this to one of:

# - "/etc/mysql/my.cnf" to set global options,

# - "~/.my.cnf" to set user-specific options.

# 

# One can use all long options that the program supports.

# Run program with --help to get a list of available options and with

# --print-defaults to see which it would actually understand and use.

#

# For explanations see

# http://dev.mysql.com/doc/mysql/en/server-system-variables.html



# This will be passed to all mysql clients

# It has been reported that passwords should be enclosed with ticks/quotes

# escpecially if they contain "#" chars...

# Remember to edit /etc/mysql/debian.cnf when changing the socket location.



# Here is entries for some specific programs

# The following values assume you have at least 32M ram



!includedir /etc/mysql/conf.d/

found here at apt-browse.org

Purge/Reinstall also did not work for me. I found the following "solution":

I could not find mysql.cnf.fallback listed in the "provided files" for mysql-server-5.6 / mysql-client-5.6 nor any additional info about the file.

I copied /etc/mysql/my.cnf to /etc/mysql/my.cnf.fallback (guessing that this would have been a relatively less important "fallback" config file);

/etc/mysql/my.cnf is a symlink, so ls /etc/mysql now shows:

 my.cnf.fallback -> /etc/alternatives/my.cnf

 my.cnf -> /etc/alternatives/my.cnf

The installation of the package then completed without error (since presumably the "doesn't exist" issue was "solved").

I have not come across any adverse effects (yet).

I had the same problem while trying to purge mysql-server (5.7.14).

In case that the my.cnf* files are missing, you can re-install the package mysql-common, and afterwards, you can purge both (mysql-server & mysql-common)

These my.cnf* files belong to mysql-common package (see bellow):

$ dpkg -L mysql-common | grep cnf

/etc/mysql/my.cnf.fallback

/etc/mysql/conf.d/mysql.cnf

1. Re-install mysql-common

apt-get install --reinstall mysql-common

2. 
   Purge mysql-common

apt-get purge mysql-common

I checked my /etc/mysql/ folder and found it to be completely empty other than an empty sub-folder conf.d.

cd /etc/

# you need to delete the empty mysql folder otherwise the ln below creates the link inside the existing mysql folder

sudo rm -r mysql

sudo ln -s ./mysql.bak/ mysql

then (courtesy of this link this link)

sudo dpkg --configure -a

and now all appears okay.

The link above also mentions --force-depends but I did not need this. It also mentions apt-get -f install but again I did not need this.

As noted by charneykaye in the comments, this approach can fail if there's some mysql processes in the background. I used:

emil-mint-desktop ~ # ps -aef | grep mysql

root      6682     1  0 16:45 ?        00:00:00 sudo mysqld_safe --skip-grant-tables

root      6683  6682  0 16:45 ?        00:00:00 /bin/sh /usr/bin/mysqld_safe --skip-grant-tables

mysql     7046  6683  0 16:45 ?        00:00:01 /usr/sbin/mysqld --basedir=/usr --datadir=/var/lib/mysql --plugin-dir=/usr/lib/mysql/plugin --user=mysql --skip-grant-tables --log-error=/var/log/mysql/error.log --pid-file=/var/run/mysqld/mysqld.pid --socket=/var/run/mysqld/mysqld.sock --port=3306 --log-syslog=1 --log-syslog-facility=daemon --log-syslog-tag=

root     21046  9812  0 17:32 pts/5    00:00:00 grep --color=auto mysql

Killed the first 3 processes (the last one is the grep call itself!) using:

kill -9 6682 8883 7046

Then remove everything mysql related:

apt remove --purge mysql-*

apt autoremove

apt autoclean

and then install:

apt install mysql-server

Then it worked.

Versions:

• Mint 18.1 (based on Ubuntu). You will need to substitute apt for apt-get for some other versions.

I found an easy solution for that:

First step: apt-get install mysql-common --reinstall

Second step: apt-get install mysql-server --reinstall

And it works!

After trying all the answers above I was able to fix this problem with:

sudo rm /etc/rc5.d/S03mysql

Then was able to run:

sudo apt purge mysql-server mysql-server-5.7 mysql-server-core-5.7

sudo apt-get -f install mysql-server --fix-missing --fix-broken

IMPORTANT NOTE

AFTER PURGING AND REMOVING MYSQL. RESTART THE MACHINE.

I REPEAT "RESTART THE MACHINE"

RESTART IS THE FINAL SOLUTION. I have spent sleepless nights figuring why it's not solving.