INSERT A NODE

 #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()