Sorting and Reversing a Linked List


This article will traverse you through few easy steps to sort a linked list. Linked list needs to be sorted for many applications in computer science.  If you haven’t already ready my article of basic knowledge for Linked List, I would recommend to go through that first. You may also be interested to check out how to delete a node form a linked list.

Sorting a Linked List

To sort a linked list, first we traverse the list searching for the node with a minimum data value. Then we remove that node and append it to another list which is initially empty. We repeat this process with the remaining list until the list becomes empty, and at the end, we return a pointer to the beginning of the list to which all the nodes are moved, as shown in Figure 1.

Figure 1: Sorting a linked list

Reversing a Linked List

To reverse a list, we maintain a pointer each to the previous and the next node, then we make the link field of the current node point to the previous, make the previous equal to the current, and the current equal to the next, as shown in Figure 2.

Figure 2 : A linked list showing the previous, current, and next nodes at some point during reversal process.

Therefore, the code needed to reverse the list is:

Therefore, the code needed to reverse the list is

Prev = NULL;
While (curr != NULL)
{
Next = curr->link;
Curr -> link = prev;
Prev = curr;
Curr = next;
}

Implementation :

Sorting a Linked List:


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

Reversing a Linked List:

/* a function to sort reverse list */
struct node *reverse(struct node *p)
{
        struct node *prev, *curr;
        prev = NULL;
        curr = p;
        while (curr != NULL)
        {
                p = p-> link;
                curr-> link = prev;
                prev = curr;
                curr = p;
        }
        return(prev);
}
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: