# Given a Linked List which is sorted, how to insert in a sorted way

### 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 question, we are given a singly linked list. We are also given an element that is to be inserted into the list. But, the given list is sorted. So, the insertion should be done in such a way that the sorted order of the linked list is not disturbed.

### Problem Statement Understanding

Suppose the given linked list is 1 -> 5 -> 9 -> 11 -> 20, and the element to be inserted is 15.

So, according to the problem, 15 should be inserted between 11 and 20, as we also have to maintain the sorted order of the list.
So, the final list is 1 -> 5 -> 9 -> 11 -> 15 -> 20.

Input: Element to be inserted - 15.

Output: Explanation: As the given list is sorted in ascending order, we have inserted 15 in an appropriate position, which maintains the sorted order of the list.

As we know, insertion and deletion in a singly linked list are very efficient, but list traversal takes O(n) time. We are going to use the list traversal, but with a few tweaks. Let us have a glance at the approach.

### Approach

The approach is going to be pretty simple. We know the given linked list is already sorted. So, to insert a new element in a sorted way, we have to find an appropriate position for the new element, such that the order is not disturbed.

We are going to traverse through the list and look for the appropriate position to insert the element. To find the position, we are going to run the loop till will find a node, say, temp, whose value is greater than the new node. The node just before temp is the appropriate node.

In the end, we are going to insert the new node just after the appropriate node.

### Algorithm

• Base Case 1 - If the list is empty, then make the new node as head.
• Base Case 2 - If the new node value is lesser than the head node, then insert it at the start, make it the head.
• Traverse through the list until the data of the next of current is less than the data of the new node. By doing this, we are looking for an appropriate position to insert the new node.
• When the loop breaks, insert the new node just after the current node:
1) New_node - > next = current - > next
2) current - > next = New_node

### Dry Run #### Code Implementation

```
#include
using namespace std;

class Node {
public:
int data;
Node* next;
};

Node* new_node)
{
Node* current;

>= new_node->data) {
}
else {

while (current->next != NULL
&& current->next->data
< new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}

Node* newNode(int new_data)
{

Node* new_node = new Node();

new_node->data = new_data;
new_node->next = NULL;

return new_node;
}

{
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}

int main()
{

Node* new_node = newNode(5);
new_node = newNode(1);
new_node = newNode(11);
new_node = newNode(9);
new_node = newNode(20);
new_node = newNode(15);
return 0;
}

```
```

class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}

void sortedInsert(Node new_node)
{
Node current;

>= new_node.data) {
}
else {

while (current.next != null
&& current.next.data < new_node.data)
current = current.next;

new_node.next = current.next;
current.next = new_node;
}
}

Node newNode(int data)
{
Node x = new Node(data);
return x;
}

void printList()
{
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}

public static void main(String args[])
{
Node new_node;
new_node = llist.newNode(5);
llist.sortedInsert(new_node);
new_node = llist.newNode(9);
llist.sortedInsert(new_node);
new_node = llist.newNode(11);
llist.sortedInsert(new_node);
new_node = llist.newNode(1);
llist.sortedInsert(new_node);
new_node = llist.newNode(20);
llist.sortedInsert(new_node);
new_node = llist.newNode(15);
llist.sortedInsert(new_node);