# Insertion Sort for Singly Linked List ### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this problem, we are given a singly linked list, and we need to sort the given list using the insertion sort technique.

Input: Output: Explanation: The given list has been sorted.

This question is not a tricky one.

Let us have a glance at the approach.

### Approach

The approach is going to be pretty simple.

• We will create an empty result singly linked list, which will be sorted.
• Then, we will traverse the given linked list, and for every node that we visit, we will insert the current node in a sorted way in our result list.
• To insert in a sorted way:
• We will traverse our result list and keep comparing every node with our current node.
• As soon as we find a node whose value is greater than the current node, we will insert the current node just before that node.
• If the current node value is greater than every other node of our result list, then we will append the current node at the end.
• To see the above process of inserting an element in a sorted list in a sorted way in more detail, check out the article link provided above in the above section.
• After complete traversal, change the head of the given linked list to the head of the result list.
• Finally, return the head.

Let’s move to the algorithm to see the approach in more depth.

### Algorithm

• Initialize the newly created sorted list as NULL.
• Traverse the given singly linked list using a pointer say current.
• For every node, while traversal, store the next of the node in a temp variable and remove all of its links.
• Insert the current node in a sorted way in the result list.
• Update current’s value with temp for further traversal.
• Once the traversal is over, update the head pointer by making it point to our result list.
• Return the head pointer.

### Dry Run  ### Code Implementation

```#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
struct node* next;
};

struct node* head = NULL;
struct node* sorted = NULL;

void push(int val)
{
/* allocate node */
struct node* newnode
= (struct node*)malloc(sizeof(struct node));
newnode->data = val;
/* link the old list off the new node */
/* move the head to point to the new node */
}
void sortedInsert(struct node* newnode)
{
/* Special case for the head end */
if (sorted == NULL || sorted->data >= newnode->data) {
newnode->next = sorted;
sorted = newnode;
}
else {
struct node* current = sorted;
/* Locate the node before the point of insertion
*/
while (current->next != NULL
&& current->next->data < newnode->data) {
current = current->next;
}
newnode->next = current->next;
current->next = newnode;
}
}

// function to sort a singly linked list
// using insertion sort
void insertionsort()
{

struct node* current = head;

// Traverse the given linked list and insert every
// node to sorted
while (current != NULL) {

// Store next for next iteration
struct node* next = current->next;

// insert current in sorted linked list
sortedInsert(current);

// Update current
current = next;
}
// Update head to point to sorted linked list
}

/* Function to print linked list */
void printlist(struct node* head)
{
while (head != NULL) {
}
printf("NULL");
}

// Driver program to test above functions
int main()
{

push(5);
push(20);
push(4);
push(3);
push(30);

printf("Linked List before sorting:\n");
printf("\n");

printf("Linked List after sorting:\n");
}
```
```#include <bits stdc++.h="">
using namespace std;

struct Node {
int val;
struct Node* next;
Node(int x)
{
val = x;
next = NULL;
}
};

public:

void push(int val)
{

Node* newnode = new Node(val);

}

{
Node* current = headref;

while (current != NULL) {

Node* temp = current->next;

sortedInsert(current);
// Update current
current = temp;
}

}

void sortedInsert(Node* newnode)
{

if (newhead == NULL || newhead->val >= newnode->val) {
}
else {
Node* current = newhead;

while (current->next != NULL
&& current->next->val < newnode->val) {
current = current->next;
}
newnode->next = current->next;
current->next = newnode;
}
}

{
while (head != NULL) {
cout << head->val << " ";
}
}
};
int main()
{

list.push(3);
list.push(1);
list.push(2);
list.push(4);
list.push(5);
cout << "Linked List before sorting" << endl;
cout << endl;
cout << "Sorted Linked List" << endl;
}
```
```public class LinkedlistIS
{

class node
{
int val;
node next;

public node(int val)
{
this.val = val;
}
}

void push(int val)
{

node newnode = new node(val);

}

{

node current = headref;

while (current != null)
{

node temp = current.next;

sortedInsert(current);

current = temp;
}

}

void sortedInsert(node newnode)
{

if (newhead == null || newhead.val >= newnode.val)
{
}
else
{
node current = newhead;

while (current.next != null && current.next.val < newnode.val)
{
current = current.next;
}
newnode.next = current.next;
current.next = newnode;
}
}

{
while (head != null)
{
System.out.print(head.val + " ");
}
}

public static void main(String[] args)
{

list.push(3);
list.push(1);
list.push(2);
list.push(4);
list.push(5);
System.out.println("Linked List before Sorting..");
}
}
```
```class Node:

def __init__(self, data):
self.data = data
self.next = None

sorted = None
while (current != None):

next = current.next
sorted = sortedInsert(sorted, current)
current = next

current = None

if (head_ref == None or (head_ref).data >= new_node.data):

else:

while (current.next != None and
current.next.data < new_node.data):

current = current.next

new_node.next = current.next
current.next = new_node

while(temp != None):

print( temp.data, end = " ")
temp = temp.next

def push( head_ref, new_data):

new_node = Node(0)
new_node.data = new_data

a = None
a = push(a, 3)
a = push(a, 1)
a = push(a, 2)
a = push(a, 4)
a = push(a, 5)

print("Linked List before sorting ")
printList(a)

a = insertionSort(a)

print("\nLinked List after sorting ")
printList(a)
```

#### Output

Linked List before Sorting.
5 4 2 1 3