Show links with catagories. Help please.

I’m currently using the Rin 1.1 theme. At the moment it lists my links in the side bar in one big list, like this;

Links
LinkFromCat1
LinkFromCat1
LinkFromCat2

What i want to do is show the catagories and then the links underneath them, like this;

Links
Cat1
LinkFromCat1
LinkFromCat1
Cat2
LinkFromCat2

I’ve tried finding an appropriate function to place in the sidebar.php, but i haven’t had any look. Right now the links part looks like;

<li><h2><?php _e('Links'); ?></h2>
   <ul>
    <?php get_links('-1', '<li>', '</li>', '<br />'); ?>
   </ul>
  </li>

Can anyone help please?