Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# INSERT A NODE

Last Updated on April 19, 2022 by Ria Pathak

Easy

### Problem Statement :

You are given a sorted linked list and you have to insert a node in the list in a sorted manner.

See original problem statement here

### EXPLANATION:

#### Approach:

If the head node is `Null`, then insert the data in the head node.

Else, if the input data is less than the start node, then insert the node at the start.

If the input data is greater than the start node, till you get the right position to insert, move the temporary pointer. If the temporary pointer’s next value is null, then insert the node at the end.

If the element lies between any two values, then connect the node to the previous node and the next node ie, `t`->`next` `=` `temp`->`next` and `temp`->`next` `=` `t`.

### SOLUTIONS:

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

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

void sortedInsert(struct Node** head_ref, struct Node* new_node)
{
struct Node* current;
{
}
else
{
while (current->next!=NULL &&
current->next->data < new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
struct Node *newNode(int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data  = new_data;
new_node->next =  NULL;

return new_node;
}
{
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
} printf("\n");
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
int n;scanf("%d",&n);
int x;scanf("%d",&x);
struct Node *new_node = newNode(x);
for(int i=1;i<n;i++)
{int x;
scanf("%d",&x);
new_node = newNode(x);
}
int m;scanf("%d",&m);
new_node = newNode(m);
}
return 0;
}

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

class Node
{
public:
int data;
Node* next;
};
{
Node* current;
{
}
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;
}
printf("\n");
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
int n;scanf("%d",&n);
int x;scanf("%d",&x);
Node *new_node = newNode(x);
for(int i=1;i<n;i++)
{int x;
scanf("%d",&x);
new_node = newNode(x);
}
int m;scanf("%d",&m);
new_node = newNode(m);
}
return 0;
}
```
```import java.io.*;
import java.util.*;
public class Main{

public int data;

this.data = nodeData;
this.next = null;
}
}

this.tail = null;
}

public void insertNode(int nodeData) {

} else {
this.tail.next = node;
}

this.tail = node;
}
}
{
while(temp!=null)
{
System.out.print(temp.data+" ");
temp=temp.next;
}
System.out.println();
}

// Special case for the head end
{
}

// 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;

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
int testCases = scanner.nextInt();

while (testCases-- > 0) {

int llistCount = scanner.nextInt();

for (int i = 0; i < llistCount; i++) {
int llistItem = scanner.nextInt();

llist.insertNode(llistItem);
}
int value= scanner.nextInt();

}

scanner.close();
}
}

```
```class Node:

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

def __init__(self):

def sortedInsert(self, new_node):

else :

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

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

def printList(self):
while(temp):
print(temp.data, end = " ")
temp = temp.next

new_node = Node(5)
llist.sortedInsert(new_node)
new_node = Node(1)
llist.sortedInsert(new_node)
new_node = Node(11)
llist.sortedInsert(new_node)
new_node = Node(9)
llist.sortedInsert(new_node)
new_node = Node(20)
llist.sortedInsert(new_node)
new_node = Node(15)
llist.sortedInsert(new_node)