# Interview Questions

Ritambhara Technologies - Coding Interview Preparations > Interview Questions > Algorithms > Sorting a linked list

# Sorting a linked list

- January 21, 2013
- Posted by: Kamal Rawat
- Category: Algorithms

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

**code:**

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

Below is the function to sort the linked list:

/** 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^{2})

Extra Space used: O(1)

ardam kaledu guru