Last Updated on April 19, 2022 by Ria Pathak
Concepts Used
Linked list
Difficulty Level
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->nextandtemp->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;
if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
current = *head_ref;
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;
}
void printList(struct Node *head)
{
struct Node *temp = head;
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);
struct Node* head = NULL;
int x;scanf("%d",&x);
struct Node *new_node = newNode(x);
sortedInsert(&head, new_node);
for(int i=1;i<n;i++)
{int x;
scanf("%d",&x);
new_node = newNode(x);
sortedInsert(&head, new_node);
}
int m;scanf("%d",&m);
new_node = newNode(m);
sortedInsert(&head, new_node);
printList(head);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node* next;
};
void sortedInsert(Node** head_ref, Node* new_node)
{
Node* current;
if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
current = *head_ref;
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;
}
void printList(Node *head)
{
Node *temp = head;
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);
Node* head = NULL;
int x;scanf("%d",&x);
Node *new_node = newNode(x);
sortedInsert(&head, new_node);
for(int i=1;i<n;i++)
{int x;
scanf("%d",&x);
new_node = newNode(x);
sortedInsert(&head, new_node);
}
int m;scanf("%d",&m);
new_node = newNode(m);
sortedInsert(&head, new_node);
printList(head);
}
return 0;
}
import java.io.*;
import java.util.*;
public class Main{
static class SinglyLinkedListNode {
public int data;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(int nodeData) {
this.data = nodeData;
this.next = null;
}
}
static class SinglyLinkedList {
public SinglyLinkedListNode head;
public SinglyLinkedListNode tail;
public SinglyLinkedList() {
this.head = null;
this.tail = null;
}
public void insertNode(int nodeData) {
SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
}
static void printLinkedList(SinglyLinkedListNode head)
{
SinglyLinkedListNode temp=head;
while(temp!=null)
{
System.out.print(temp.data+" ");
temp=temp.next;
}
System.out.println();
}
static SinglyLinkedListNode insertSortedNode(SinglyLinkedListNode head,int value) {
//write your code here
// Special case for the head end
SinglyLinkedListNode newNode = new SinglyLinkedListNode(value);
if (head == null || head.data >= newNode.data)
{
newNode.next = head;
head = newNode;
return head;
}
// Locate the node before the point of insertion
SinglyLinkedListNode current = head;
while (current.next != null && current.next.data < newNode.data) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
return head;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
int testCases = scanner.nextInt();
while (testCases-- > 0) {
SinglyLinkedList llist = new SinglyLinkedList();
int llistCount = scanner.nextInt();
for (int i = 0; i < llistCount; i++) {
int llistItem = scanner.nextInt();
llist.insertNode(llistItem);
}
int value= scanner.nextInt();
printLinkedList(insertSortedNode(llist.head,value));
}
scanner.close();
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def sortedInsert(self, new_node):
if self.head is None:
new_node.next = self.head
self.head = new_node
elif self.head.data >= new_node.data:
new_node.next = self.head
self.head = new_node
else :
current = self.head
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):
temp = self.head
while(temp):
print(temp.data, end = " ")
temp = temp.next
llist = LinkedList()
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)
print("Create Linked List", end=" ")
llist.printList()
[forminator_quiz id="1793"]
This article tried to discuss Linked list. Hope this blog helps you understand and solve the problem. To practice more problems on Linked list you can check out MYCODE | Competitive Programming.