INSERT A NODE

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

Leave a Reply

Your email address will not be published. Required fields are marked *