# 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.

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.

### Dry Run  ### Code Implementation

```#include
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);

}

{

while (current != NULL) {

Node* temp = current->next;

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

}

void sortedInsert(Node* newnode)
{

}
else {

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

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

}

{

while (current != null)
{

node temp = current.next;

sortedInsert(current);

current = temp;
}

}

void sortedInsert(node newnode)
{

{
}
else
{

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

{
{
}
}

public static void main(String[] args)
{

list.push(3);
list.push(1);
list.push(2);
list.push(4);
list.push(5);
}
}
```