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, refer some online coding classes and 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;  
    }   
 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();
    }
     }

Previous post Valid Binary Search Tree
Next post PALINDROME LIST

Leave a Reply

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