I ran into this problem yesterday after someone rebooted during an OS version upgrade. None of the approaches worked above because of the sheer scale of the mess ups (~1500 packages).
To recover I went to
/var/log/apt/history.log and looked at the last entry which has three very long lists describing what was being attempted when the OS upgrade failed. It consists of three lists "Upgrade:" "Install:" "Remove:" of the form:
Upgrade: package1:arch (old, new), package2:arch (old, new),
Take those three lists into your favourite regexp compatible editor, and replace the parentheses up to the comma with a newline. For the "Remove:" section append a "-" so you're left with lists like:
The "-" was a key learning because unless you can tell it to both install and remove you won't be able to work your way past many of the dependency cycles.
Keep a copy of this file so you can refer to it later, but make a new copy where you clean it up: remove all the extra lines of the file leaving just the
Run apt using that resulting file packages.txt as follows
xargs -a packages.txt sudo apt install
This command will be all the adds/removes that the system intended to do before it got broken, and should represent a consistent set.
Assuming it finishes you can then complete anything missed with
sudo apt install -f and
sudo apt dist-upgrade.
Finish by creating a new list with just the "Install:" list of packages, pass them to
apt-mark auto to mark the packages as automatically installed (the upgrade chose them, not you).
xargs -a installed.txt sudo apt-mark auto
I hope that helps someone else out there who thought their whole system was borked.