Sorting a linked list

Write a function to sort the given unsorted linked list.

Input list:  6 -> 7 -> 0 -> 1 -> 8 -> 2 -> 4 -> 3
Output list: 0 -> 1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8

Solution:

This is a standard algorithm using insertion sort to sort a linked list. Earlier we have discussed a post to "Insert in a sorted linked list". This algorithm will use the algorithm given in this post.

1. resultList = NULL;
2. For each Node in the list
   a. Delete Node from the list
   b. Insert the deleted Node in the list in a sorted manner.
3. Return resultList

First lets modify the function given in this post to insert in a sorted linked list.

/** Insert element in a sorted linked list.
 * Element will be inserted in sorted manner only.
 *  newNode - pointer to the node to be inserted
 */
void insertSorted(Node**head, Node* newNode)
{
    // Nothing to insert.. boundary check.
    if(newNode == NULL)
        return;
    // Inserting at the head of the list.
    if(*head == NULL || (*head)->data > newNode->data)
    {
        newNode->link = *head;
        *head = newNode;
        return;
    }
    // Inserting anywhere else.
    Node* temp = *head;
    // Moving to the point where insertion need to be done.
    while( temp->link != NULL && temp->link->data < newNode->data )
    {
        temp = temp->link;
    }
    newNode->link =  temp->link;
    temp->link = newNode;
}

/** Sort a Singly linked list.
 *  While traversing the list, delete each node from the list and
 *  insert it in the result list in sorted manner.
 */
void sortList(Node** head)
{
    if(head == NULL || (*head)->data == NULL)
        return;
    Node* temp = *head;
    Node* result = NULL;
    // for each node in the list.
    Node* np = *head;
    while(np != NULL)
    {
        Node * temp = np->link;
        insertSorted(&result, np);
        np = temp;
    }
    *head = result;
}

Time Complexity: O(n²)

Extra Space used: O(1)