# Insert Node in the Sorted Linked List  Difficulty Level Easy

## Problem Statement  In the “Insert Node in the Sorted Linked List” problem we have given a linked list. Insert a new node in the sorted linked list in a sorted way. After inserting a node in the sorted linked list the final linked list should be the sorted linked list.

## Example  ```4 7 10
3 5 15```
`3 4 5 7 10 15`

## Approach  We have to insert a node in the sorted linked_list such that after inserting the node in the linked_list it will remain sorted. We have to place the node in the correct position.

We have to create a new node with the value that we want to insert in the linked list. Iterate through the linked to find the correct position. We iterate through the linked list until the value of nodes in the linked list is less than the value that we want to insert in the linked list. We also store a previous node that has a value less than the value of the new node that we have to insert. After we find the curr node which has a value greater than the new node value.

Then the next pointer to the new_node points to the curr node. Since the value of curr node is greater than the new_node. Then if the prev node is null, that means the new_node is the smallest node then it must be positioned at the beginning of the linked list. So we point the head to this node. If the pre is not null then we link the previous next to the new_node.

## Algorithm  1. Create a node with the value that we want to insert in the linked list.
2. Create two pointers curr and prev, curr points to the head node and pre is initially null.
3. Iterate the linked list until the nodes have a value less than the new_node value.
4. Points new_node next to the curr node,
5. If the pre node is null, then the head node points to this node, else prev next is the new_node.

## Explanation  ### C++ program to Insert Node in the Sorted Linked List

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

public:
struct ListNode {
ListNode *next;
int val;
ListNode(int a): next(NULL), val(a){}
};

}

ListNode *node = new ListNode(val);
}

void sortedInsert(int val){
ListNode* node = new ListNode(val);
ListNode* pre = NULL;

while(curr!=NULL && val>curr->val){
pre = curr;
curr = curr->next;
}

node->next = curr;
if(pre==NULL){
}else{
pre->next = node;
}
}

void print_list(){
while(node){
cout<<node->val<<" ";
node = node->next;
}
cout<<endl;
}
};

int main(){
list->print_list();
list->sortedInsert(5);
list->sortedInsert(3);
list->sortedInsert(15);

list->print_list();
}```

### Java Program to Insert Node in the Sorted Linked List

```import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{

public static void main (String[] args) throws java.lang.Exception{

obj.printList();

obj.sortedInsert(2);
obj.sortedInsert(5);
obj.sortedInsert(15);
obj.printList();

}

class Node{
Node next = null;
int val = 0;

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

private int size;

this.size = 0;
}

public Node getNodeAt(int index){
while(index-- > 0){
curr = curr.next;
}

return curr;
}

Node node = new Node(val);
if(this.size == 0){
}
else{
}
this.size++;
}

public void sortedInsert(int val) {
Node newNode = new Node(val);
Node previous = null;

while (current != null && val > current.val) {
previous = current;
current = current.next;
}

newNode.next = current;
if (previous == null)
else
previous.next = newNode;

}

public void printList(){
while(curr!=null){
System.out.print(curr.val+" ");
curr = curr.next;
}
System.out.println("");
}

}
}```
```4 6 7
2 5```
`2 4 5 6 7`

## Complexity Analysis to Insert Node in the Sorted Linked List  ### Time Complexity

O(n) where n is the number of nodes present in the linked list. Here we simply traverse the linked list from the starting and add the node to its correct position.