Display Category name only once

I’m building a list in a single-post template—I need to list all posts that have the current tag, along with their category. All posts that have the current tag will only have one category. My problem is that I only want the category name to display once per category. I also need them grouped by category, so the end result will look like this:

CATEGORY1
POST1
POST2
POST3
CATEGORY2
POST4
POST5
POST6

My current code looks like this:

<?php

                   $tags = wp_get_post_tags($post->ID);
                   if ($tags) {
                   $first_tag = $tags[0]->term_id;
                   $args=array(
                   'tag__in' => array($first_tag),
                   'post__not_in' => array($post->ID),
                   );

                   $my_query = new WP_Query($args);
                   if( $my_query->have_posts() ) {
                   while ($my_query->have_posts()) : $my_query->the_post(); ?>

                            <li>

                           <?php
                            foreach((get_the_category()) as $category) {
                                echo $category->cat_name . ' ';
                            }
                            ?></li>

                        <li><a href="<?php the_permalink() ?>" rel="bookmark" title="Permanent      Link to <?php the_title_attribute(); ?>">
                   <?php the_title(); ?></a>

                   <?php endwhile; }
                   wp_reset_query();
                   }
                   ?>

This results in:

CATEGORY1
POST1
CATEGORY1
POST2
CATEGORY2
POST3
CATEGORY1
POST4
CATEGORY2
POST5

Etc…

So I need to 1) organize everything by category, and 2) display that category name only once. My PHP skills are minimal, and I’m at a total loss as to how to accomplish this. Any help is appreciated.