Find the Second Smallest Element in a Linked List

Find the second smallest element of linked list with minimum iteration. We are assume that linked list is combination of integer value nodes. And linked list node can be hold any integer value like negative or positive.

implementation approach : We can solve this problem in a two ways.

Method A : First approach are sorted a linked list element in ascending order then find second smallest element. But note that is process are required modification of existing linked list. And arrangement of linked list element in sorted view it will take more than O(n) time to sort element. so we can solve this problem in second approach.

Method B: Suppose we are find first smallest element of linked list, then we can solve this problem very easily by using linked list iteration front node to last node and compare the node values.

We can modified this approach to finding a second last node of linked list. We are tack two integers or two pointers as you wise you can take any one. Our goal is to find second smallest node by using first smallest element. Before view the solution of this problem. Apply your logic and write an algorithm which will satisfy the following test cases.

1) When linked list are empty then display proper message like ( empty linked list etc).

2) When linked list are contain only one nodes then we cannot find second smallest element. So in this case also display a message like (Only one node of linked list etc).

3) When every similar nodes are exist in linked list in this situation, smallest node is an second smallest value.

Linked list : 1->1->1->NULL
Result : 1

We can modified this situation when all similar nodes. But in this case above result are accepting.

4) There can be possible duplicates nodes are exist in linked list. In this situation there are also possible to two smallest element. for example.

Linked list : 1->2->1->3->NULL (2 smallest 1)
Result : 2

We are find other second smallest node which are existing in linked list.

Suppose we are inserted the following (7, 1, 4, 2, 5, 3 , 1 ) node in a sequence.

Find the Second Smallest Element in a Linked List

Here given code implementation process.

//C Program
//Find the Second Smallest Element in a Linked List
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
  int data;
  struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
//insert Node element
void insert(struct Node**head,int value){
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL){
    printf("Memory overflow\n");
  }else{
    node->data=value;
    node->next=NULL;
    if(*head==NULL){
      *head=node;
    }else{
      struct Node*temp=*head;
      //find last node
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add node at last possition
      temp->next=node;
    }
  }
}
//find second smallest element in linked list node
void second_smallest(struct Node*temp){

  if(temp!=NULL){

      if(temp->next==NULL){
        printf("Only one node of linked list\n");
      }else{

       struct Node*first=NULL,*second=NULL;
        if(temp->data > temp->next->data){
            first=temp->next;
            second=temp;
        }else{
          first=temp;
          second=temp->next;
        }
        while(temp!=NULL){
          if(temp->data<first->data){
            //Get smallest node

            if(second->data>first->data){
              //find new smallest node
              second=first;
            }
            first=temp; 
          }else if(temp->data<second->data && temp->data>first->data){
            //when node value greater than smallest value but less than second node value
            second=temp;
          }else if(first->data==second->data && temp->data > first->data){
            //When first and second are same value nodes
            //and next upcomming are our second node
            second=temp;
          }
          temp=temp->next;
        }
        printf("\nSecond smallest : %d\n",second->data);
      }

  }else{
    printf("Empty Linked List\n");
  }

}
//Display element of Node
void display(struct Node*temp){
  
  if(temp==NULL){
    printf("Empty linked list");
  }
  while(temp!=NULL){
    printf("%d  ",temp->data);
    temp=temp->next;
  }
}
int main(){
  //create node pointer
  struct Node*head=NULL;
  //insert element of linked list


  insert(&head,7);
  insert(&head,1);
  insert(&head,4);
  insert(&head,2);
  insert(&head,5);
  insert(&head,3);
  insert(&head,1);
  //display all node
  display(head);
  second_smallest(head);
  return 0;
}

Output

7  1  4  2  5  3  1  
Second smallest : 2
//C++ Program 
//Find the Second Smallest Element in a Linked List
#include<iostream>
using namespace std;

//create structure
struct Node{
  int data;
  struct Node*next;
};
class LinkedList{
  Node*head;//head node
  public:
    LinkedList();
    void insert(int);
    void display();
    void second_smallest();
};
LinkedList::LinkedList(){
  head=NULL;
}
//insert node at end of linked list
void LinkedList::insert(int value){
    //Create dynamic node
  struct Node*node=new Node;
  if(node==NULL){
    cout<<"Memory overflow\n";
  }else{
    node->data=value;
    node->next=NULL;
    if(head==NULL){
      //base condition
      head=node;
    }else{
      Node*temp=head;
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add newly node at last
      temp->next=node;
    }
  }
}
//display all node value in linked list
void LinkedList:: display(){
  if(head==NULL){
    cout<<"Empty linked list";
  }
  else{
    Node*temp=head;
    cout<<"Linked List : ";
    while(temp!=NULL){
      //print node value
      cout<<temp->data<<" ";
      temp=temp->next;
    }
  }

}
//find second smallest element in linked list node
void LinkedList:: second_smallest(){
  struct Node*temp=head;
  if(temp!=NULL){

      if(temp->next==NULL){
        cout<<"Only one node of linked list"<<endl;
      }else{

        struct Node*first=NULL,*second=NULL;
        if(temp->data > temp->next->data){
            first=temp->next;
            second=temp;
        }else{
          first=temp;
          second=temp->next;
        }
        
        while(temp!=NULL){
          if(temp->data<first->data){
            //Get smallest node

            if(second->data>first->data){
              //find new smallest node
              second=first;
            }

            first=temp; 
          }else if(temp->data<second->data && temp->data>first->data){
            //when node value greater than smallest value but less than second node value
            second=temp;
          }
          else if(first->data==second->data && temp->data > first->data){
            //When first and second are same value nodes
            //and next upcomming are our second node
            second=temp;
          }
          temp=temp->next;
        }
        cout<<"\nSecond smallest : "<<second->data<<endl;
      }

  }else{
    cout<<"Empty Linked List"<<endl;
  }

}
int main(){
 
  //create object
  LinkedList obj;
  //insert element of linked list
  obj.insert(7);
  obj.insert(1);
  obj.insert(4);
  obj.insert(2);
  obj.insert(5);
  obj.insert(3);
  obj.insert(1);

  //display all node
  obj.display();
  obj.second_smallest();
  return 0;
}

Output

Linked List : 7 1 4 2 5 3 1 
Second smallest : 2
//Java Program
//Find the Second Smallest Element in a Linked List
public class LinkedList{

  static class Node{
    int data;
    Node next;
  }
  static Node head;
    //Class constructors
  LinkedList(){
    head=null;
  } 
    //insert element
  public void insert(int value){
      //Create  node
    Node node=new Node();
    node.data=value;
    node.next=null;
    if(head==null) head=node;
    else{
      Node temp=head;
          //find last node
      while(temp.next!=null){
        temp=temp.next;
      }
      temp.next=node;
    }

  }
   //Display all Linked List elements
  public void display(){
    if(head!=null){
      System.out.print("Linked List Element :");
      Node temp=head;
      while(temp!=null){
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
    }else{
      System.out.println("Empty Linked list"); 
    }
  }
    //find second smallest element in linked list node
  public void second_smallest(){

    if(head!=null){
      Node temp=head;
      if(temp.next==null){
        System.out.println("Only one node of linked list\n");
      }else{

        Node first=null, second=null;
        if(temp.data > temp.next.data){
          first=temp.next;
          second=temp;
        }else{
          second=temp.next;
          first=temp;
        }
        
        while(temp!=null){
          if(temp.data<first.data){
                  //Get smallest node

            if(second.data>first.data){
                      //find new smallest node
              second=first;
            }
            first=temp; 
          }else if(temp.data<second.data && temp.data>first.data){
                  //when node value greater than smallest value but less than second node value
            second=temp;
          }else if(first.data==second.data && temp.data > first.data){
            //When first and second are same value nodes
            //and next upcomming are our second node
            second=temp;
          }
          temp=temp.next;
        }
        System.out.print("\nSecond smallest : "+second.data);
      }

    }else{
      System.out.println("\nEmpty Linked List");
    }

  }
  public static void main(String[] args) {

    LinkedList obj=new LinkedList();
    //insert element of linked list
    obj.insert(7);
    obj.insert(1);
    obj.insert(4);
    obj.insert(2);
    obj.insert(5);
    obj.insert(3);
    obj.insert(1);

    //display all node
    obj.display();
    //find second smallest node
    obj.second_smallest();
  }
}

Output

Linked List Element :  7  1  4  2  5  3  1
Second smallest : 2
#Python Program
#Find the Second Smallest Element in a Linked List
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None

#Create Class Linked    
class Linked:
    def __init__(self):
        #Assign default value
        self.head=None

    #insert new node to linked list  
    def insert(self,data):
        node=Node(data)
        node.next=None
        if self.head==None:
            self.head=node
        else:
            temp=self.head
            while temp.next!=None:
                temp=temp.next
            #add node    
            temp.next=node

    def display(self):
        if(self.head==None):
            print("Empty Linked List")
            return

        temp=self.head
        print("Linked List Elements : ")
        while(temp!=None):
          print(temp.data,end=" ")
          temp=temp.next
 
    #find second smallest element in linked list node
    def second_smallest(self):
        if(self.head!=None):
            temp=self.head
            if(temp.next==None):
                print("Only one node of linked list\n")
            else:

                first=None
                second=None
                if(temp.data > temp.next.data):
                    first=temp.next
                    second=temp
                else:
                    second=temp.next
                    first=temp
                
                while(temp!=None):
                    if(temp.data<first.data):
                        #Get smallest node

                        if(second.data>first.data):
                            #find new smallest node
                            second=first
                        
                        first=temp 
                    elif(temp.data<second.data and temp.data>first.data):
                        #when node value greater than smallest value 
                        #but less than second node value
                        second=temp
                    elif(temp.data>first.data and first.data==second.data):
                        second=temp    
                    
                    temp=temp.next
                
                print("\nSecond smallest : ",second.data)
            

        else:
            print("\nEmpty Linked List")
        

    
def main():
    #Create Object of class Linked
    obj=Linked()
    #insert element of linked list
    obj.insert(7)
    obj.insert(1)
    obj.insert(4)
    obj.insert(2)
    obj.insert(5)
    obj.insert(3)
    obj.insert(1)

    #display all node
    obj.display()
    #find second smallest node
    obj.second_smallest()
    
if __name__=="__main__":
    main()

Output

Linked List Elements : 
7 1 4 2 5 3 1 
Second smallest :  2
//C# Program
//Find the Second Smallest Element in a Linked List
using System;
class LinkedList{

    public class Node{
        public int data;
        public Node next;
    }
    public static Node head;
    //Class constructors
    LinkedList(){
        head=null;
    } 
    //insert element
    public void insert(int value){
        //Create  node
        Node node=new Node();
        node.data=value;
        node.next=null;
        if(head==null) head=node;
        else{
            Node temp=head;
            //find last node
            while(temp.next!=null){
                temp=temp.next;
            }
            temp.next=node;
        }

    }
    //Display all Linked List elements
    public void display(){
        if(head!=null){
            Console.Write("Linked List Element :");
            Node temp=head;
            while(temp!=null){
                Console.Write(" {0}",temp.data);
                temp=temp.next;
            }
        }else{
            Console.WriteLine("Empty Linked list"); 
        }
    }
    //find second smallest element in linked list node
    public void SecondSmallest(){

        if(head!=null){
            Node temp=head;
            if(temp.next==null){
                Console.WriteLine("Only one node of linked list\n");
            }else{


                Node first=null, second=null;
                if(temp.data > temp.next.data){
                    first=temp.next;
                    second=temp;
                }else{
                    second=temp.next;
                    first=temp;
                }
                while(temp!=null){
                    if(temp.data<first.data){
                        //Get smallest node

                        if(second.data>first.data){
                            //find new smallest node
                            second=first;
                        }
                        first=temp; 
                    }else if(temp.data<second.data && temp.data>first.data){
                        //when node value greater than smallest value but less than second node value
                        second=temp;
                    }
                    else if(first.data==second.data && temp.data > first.data){
                        //When first and second are same value nodes
                        //and next upcomming are our second node
                        second=temp;
                    }
                    temp=temp.next;
                }
                Console.WriteLine("\nSecond smallest : {0}",second.data);
            }

        }else{
            Console.WriteLine("\nEmpty Linked List");
        }

    }
    public static void Main() {

        LinkedList obj=new LinkedList();
        //insert element of linked list
        obj.insert(7);
        obj.insert(1);
        obj.insert(4);
        obj.insert(2);
        obj.insert(5);
        obj.insert(3);
        obj.insert(1);

        //display all node
        obj.display();
        //find second smallest node
        obj.SecondSmallest();
    }
}

Output

Linked List Element : 7 1 4 2 5 3 1
Second smallest : 2
<?php
//Php program 
//Find the Second Smallest Element in a Linked List
class Node
{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data = $data;
    $this->next = NULL;
  }
}
class LinkedList{

    private $head;
    function __construct()
    {
      $head=NULL;
    }
    /*
    * Append the Given data value at end of linked list
    * Fun : insert
    * Parm: data value
    *@return None
    */
    function insert($data)
    {
      $newNode=new Node($data); 
      if($this->head==NULL)
      {
        $this->head=$newNode;
      }else{
        $temp=$this->head;
            //find last node of linked list
        while($temp->next!=NULL){
          $temp=$temp->next;
        }
            //add new node to last of linked list
        $temp->next=$newNode;
      }
    }
    //Display all inserted node in linked list
    function display()
    {
      if($this->head==NULL)
      {
        echo "Empty Linked List";
      }
      else{
        $temp=$this->head;
        echo "Linked List :";
        while($temp!=NULL)
        {
          //display node value
          echo "  ".$temp->data;
          //visit to next node
          $temp=$temp->next; 
        }
      }   
    }
    //find second smallest element in linked list node
    function second_smallest()
    {

      if($this->head!=NULL)
      {
        $temp=$this->head;

        if($temp->next==NULL)
        {
          echo "Only one node of linked list<br>";
        }else
        {

          $first=NULL;
          $second=NULL;
          if($temp->data>$temp->next->data){
            $first=$temp->next;
            $second=$temp;
          }else{
            $first=$temp;
            $second=$temp->next;
          }
          while($temp!=NULL){
            if($temp->data<$first->data)
            {
                //Get smallest node


              if($second->data>$first->data)
              {
                  //find new smallest node
                $second=$first;
              }

              $first=$temp; 
            }else if($temp->data<$second->data && $temp->data>$first->data)
            {
                //when node value greater than smallest value but less than second node value
              $second=$temp;
            }
            else if($temp->data>$second->data && $second->data==$first->data)
            {
                
              $second=$temp;
            }
            $temp=$temp->next;
          }
          echo "<br>Second smallest : ".$second->data;
        }

      }
      else
      {
        echo "Empty Linked List<br>";
      }

    }
  }
  function main(){
  //Make a object of LinkedList class
    $obj= new LinkedList();

  /*
  *Insert following nodes in linked list
  */
  $obj->insert(7);
  $obj->insert(1);
  $obj->insert(4);
  $obj->insert(2);
  $obj->insert(5);
  $obj->insert(3);
  $obj->insert(1);
  $obj->display();
  $obj->second_smallest();
}
main();
?>

Output

Linked List : 7 1 4 2 5 3 1
Second smallest : 2

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved