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

### Like this:

Like Loading...

*Related*