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

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
//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;
}else{
//find last node
while(temp->next!=NULL){
temp=temp->next;
}
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{
}

}
//Display element of Node
void display(struct Node*temp){

if(temp==NULL){
}
while(temp!=NULL){
printf("%d  ",temp->data);
temp=temp->next;
}
}
int main(){
//create node pointer

//display all node
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;
};
public:
void insert(int);
void display();
void second_smallest();
};
}
//insert node at end of linked list
//Create dynamic node
struct Node*node=new Node;
if(node==NULL){
cout<<"Memory overflow\n";
}else{
node->data=value;
node->next=NULL;
//base condition
}else{
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=node;
}
}
}
//display all node value in linked list
}
else{
while(temp!=NULL){
//print node value
cout<<temp->data<<" ";
temp=temp->next;
}
}

}
//find second smallest element in linked list node
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{
}

}
int main(){

//create object
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

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

}
public void display(){
while(temp!=null){
System.out.print("  "+temp.data);
temp=temp.next;
}
}else{
}
}
//find second smallest element in linked list node
public void second_smallest(){

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{
}

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

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

def __init__(self):
#Assign default value

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

def display(self):
return

while(temp!=None):
print(temp.data,end=" ")
temp=temp.next

#find second smallest element in linked list node
def second_smallest(self):
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:

def main():
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;

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

}
public void display(){
while(temp!=null){
Console.Write(" {0}",temp.data);
temp=temp.next;
}
}else{
}
}
//find second smallest element in linked list node
public void SecondSmallest(){

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{
}

}
public static void Main() {

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

function __construct()
{
}
/*
* Append the Given data value at end of linked list
* Fun : insert
* Parm: data value
*@return None
*/
function insert(\$data)
{
\$newNode=new Node(\$data);
{
}else{
//find last node of linked list
while(\$temp->next!=NULL){
\$temp=\$temp->next;
}
\$temp->next=\$newNode;
}
}
//Display all inserted node in linked list
function display()
{
{
}
else{
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(\$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
{
}

}
}
function main(){
//Make a object of LinkedList class

/*
*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.