Insert Node in the Sorted Linked List

Problem Statement

In the “Insert Node in the Sorted Linked List” problem we have given a linked list. Insert a new node in the sorted linked list in a sorted way. After inserting a node in the sorted linked list the final linked list should be the sorted linked list.

Example

4 7 10 
3 5 15

3 4 5 7 10 15

Approach

We have to insert a node in the sorted linked_list such that after inserting the node in the linked_list it will remain sorted. We have to place the node in the correct position. 

We have to create a new node with the value that we want to insert in the linked list. Iterate through the linked to find the correct position. We iterate through the linked list until the value of nodes in the linked list is less than the value that we want to insert in the linked list. We also store a previous node that has a value less than the value of the new node that we have to insert. After we find the curr node which has a value greater than the new node value.

Then the next pointer to the new_node points to the curr node. Since the value of curr node is greater than the new_node. Then if the prev node is null, that means the new_node is the smallest node then it must be positioned at the beginning of the linked list. So we point the head to this node. If the pre is not null then we link the previous next to the new_node.

Algorithm

1. Create a node with the value that we want to insert in the linked list.
2. Create two pointers curr and prev, curr points to the head node and pre is initially null.
3. Iterate the linked list until the nodes have a value less than the new_node value.
4. Points new_node next to the curr node,
5. If the pre node is null, then the head node points to this node, else prev next is the new_node.

Explanation

C++ program to Insert Node in the Sorted Linked List

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

class MyLinkedList {
public:
    struct ListNode {
        ListNode *next;
        int val;
        ListNode(int a): next(NULL), val(a){}
    };
    ListNode *head;

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(int val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    void sortedInsert(int val){
        ListNode* node = new ListNode(val);
        ListNode* pre = NULL;
        ListNode *curr = head;

        while(curr!=NULL && val>curr->val){
            pre = curr;
            curr = curr->next;
        }

        node->next = curr;
        if(pre==NULL){
            head = node;
        }else{
            pre->next = node;
        }
    }

    void print_list(){
    	ListNode* node = head;
    while(node){
      cout<<node->val<<" ";
      node = node->next;
    }
        cout<<endl;
  }
};


int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead(10);
  list->addAtHead(7);
  list->addAtHead(4);
  list->print_list();
    list->sortedInsert(5);
    list->sortedInsert(3);
    list->sortedInsert(15);

    list->print_list();
}

Java Program to Insert Node in the Sorted Linked List

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
  
  public static void main (String[] args) throws java.lang.Exception{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead(10);
    obj.addAtHead(7);
    obj.addAtHead(4);
    obj.printList();
    
    obj.sortedInsert(2);
    obj.sortedInsert(5);
    obj.sortedInsert(15);
    obj.printList();
    
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          int val = 0;
          
          public Node(int val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      public Node getNodeAt(int index){
          Node curr = head;
          while(index-- > 0){
              curr = curr.next;
          }
          
          return curr;
      }
      
      public void addAtHead(int val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
      public void sortedInsert(int val) {
          Node newNode = new Node(val);
          Node previous = null;
          Node current = head;
  
          while (current != null && val > current.val) {
              previous = current;
              current = current.next;
          }
  
          newNode.next = current;
      if (previous == null)
          head = newNode;
      else
          previous.next = newNode;
  
      }

    public void printList(){
      Node curr = head;
      while(curr!=null){
        System.out.print(curr.val+" ");
        curr = curr.next;
      }
      System.out.println("");
    }
      
  }
}

4 6 7
2 5

2 4 5 6 7

Complexity Analysis to Insert Node in the Sorted Linked List

Time Complexity

O(n) where n is the number of nodes present in the linked list. Here we simply traverse the linked list from the starting and add the node to its correct position.

Space Complexity

O(1) because we don’t create any auxiliary space. Here we add a node at its desire place without the use of any extra space.