How to sort a singly linked list?


Sorting a singly linked is simple. Find the method below for the same.

/* a function to sort a list */
struct node *sortlist(struct node *p)
{
        struct node *temp1,*temp2,*min,*prev,*q;
        q = NULL;
        while(p != NULL)
        {
                prev = NULL;
                min = temp1 = p;
                temp2 = p -> link;
                while ( temp2 != NULL )
                {
                        if(min -> data > temp2 -> data)
                        {
                                min = temp2;
                                prev = temp1;
                        }
                        temp1 = temp2;
                        temp2 = temp2-> link;
                }
                if(prev == NULL)
                        p = min -> link;
                else
                        prev -> link = min -> link;
                min -> link = NULL;
                if( q == NULL)
                        q = min; /* moves the node with lowest data value in the list
                                    pointed to by p to the list
                                    pointed to by q as a first node*/
                else
                {
                        temp1 = q;
                        /* traverses the list pointed to by q to get pointer to its
                           last node */
                        while( temp1 -> link != NULL)
                                temp1 = temp1 -> link;
                        temp1 -> link = min; /* moves the node with lowest data value
                                                in the list pointed to
                                                by p to the list pointed to by q at the end of list pointed by
                                                q*/
                }
        }

Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: