You can do it in one view as the content for the first list is contained in the second list.
Your view needs to bring in only the second list. You will then override one of the theme functions for your view

probably one in the list of 'Style Output'.

As you can see from this code, it prints out the HTML list format:
<?php print $wrapper_prefix; ?>
<?php if (!empty($title)) : ?>
<h3><?php print $title; ?></h3>
<?php endif; ?>
<?php print $list_type_prefix; ?>
<?php foreach ($rows as $id => $row): ?>
<li class="<?php print $classes_array[$id]; ?>"><?php print $row; ?></li>
<?php endforeach; ?>
<?php print $list_type_suffix; ?>
<?php print $wrapper_suffix; ?>
You will treat this code as printing out the second list, so you have to add code to this to print out the first list. You will have to dig through the variables available in the template to find the Category field for each row and isolate it. If the row has already been fully rendered and you don't have access to the category variable, you can then either parse out the category out of the row, or look into the row style output
views templates.
Alternatively, you could overrride one of the views hooks that fires after the sql has been run but before the rendering has taken place (hook_views_post_execute is a likely candidate). You will loop through the result and load all of the categories into a list which you then add as an attachment before ($view->attachment_before) the view.