# Insertion Sort for Singly Linked List

## Given a linked list, write a function that will sort the linked list using Insertion Sort.

### Example

INPUT :
23 ->1 ->50 ->15 ->16 ->6

OUTPUT :
1 ->6 ->15 ->16 ->23 ->50

Time Complexity : O()

## Algorithm

1. Create a list "result" to store the sorted list

2. Traverse the given list
a. Insert current node in sorted way in result list

3. Print the result list

The above Algorithm can be clearly explained in below diagram

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

struct LLNode{
int data;
LLNode *next;
};
// Prototype
void sortedInsert(LLNode**, LLNode*);

// function to sort a singly linked list using insertion sort
{
LLNode *result = NULL;

// Traverse the given list
while (curr != NULL)
{
// Store next for next iteration
LLNode *next = curr->next;

// insert current in result linked list
sortedInsert(&result, curr);

// Update current
curr = next;
}

// return the result list
return result;
}

//Insering the node in correct position in result list
void sortedInsert(LLNode** result, LLNode* new_Node)
{
LLNode* temp;
//If there is no element in result list
if (*result == NULL || (*result)->data >= new_Node->data)
{
new_Node->next = *result;
*result = new_Node;
}
else
{
//finding the position to insert the node
temp = *result;
while (temp->next!=NULL && temp->next->data < new_Node->data)
{
temp = temp->next;
}
new_Node->next = temp->next;
temp->next = new_Node;
}
}
{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

LLNode *head = NULL; //initial list has no elements
LLNode* result = NULL;

cout<<"\nCurrent List is :-\n";