Link list with multiple categories and classes

I’m trying display my links list like this, with multiple link categories mixed together, showing the most recently updated first and with the link category as a class:

<ul>
<li class="cat1"><a href="example1.com">Link 1</a></li>
<li class="cat2"><a href="example2.com">Link 2</a></li>
<li class="cat2"><a href="example3.com">Link 3</a></li>
<li class="cat4"><a href="example4.com">Link 4</a></li>
<li class="cat3"><a href="example5.com">Link 5</a></li>
<ul>

Is there any way to do this? This would get me close, but I have no idea how to add the category to the class:

<?php get_links('-1', '<li class=>', '</li>', '', FALSE, '_id', FALSE,
FALSE, 5, FALSE); ?>

I’ve also tried this (using the Link Manager to define the category class values), but the foreach ends up grouping them by category:

<?php
$link_cats = $wpdb->get_results("SELECT cat_id, cat_name FROM $wpdb->linkcategories");
foreach ($link_cats as $link_cat) {
wp_get_links($link_cat->cat_id);
} ?>