Archive for November, 2010

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

Leave a comment

How to insert a node in a sorted linked list?


To insert a new node into an already sorted list, we compare the data value of the node to be inserted with the data values of the nodes in the list starting from the first node. This is continued until we get a pointer to the node that appears immediately before the node in the list whose data value is greater than the data value of the node to be inserted.


/* 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*/
                }
        }
        return (q);
}

Leave a comment