Given a Linked list of integer data. The task is to write a program that efficiently finds the second smallest element present in the Linked List.
Examples:
Input : List = 12 -> 35 -> 1 -> 10 -> 34 -> 1
Output : The second smallest element is 10.
Input : List = 10 -> 5 -> 10
Output : The second largest element is 10.
A Simple Solution will be to first sort the linked list in ascending order and then print the second element from the sorted linked list. The time complexity of this solution is O(nlogn).
New Approach:
- Check if the linked list has at least two nodes. If not, return INT_MAX to indicate that there is no second smallest element in the list.
- Create an array arr of size 2 to store the smallest and second smallest elements seen so far.
- Initialize arr[0] and arr[1] to the data values of the first two nodes in the list, sorted in ascending order.
- Traverse the rest of the linked list, starting from the third node.
- For each node curr, compare its data value with the values in arr as follows:
- a. If curr->data is less than arr[0], set arr[1] to arr[0] and arr[0] to curr->data.
- b. Otherwise, if curr->data is less than arr[1] and not equal to arr[0], set arr[1] to curr->data.
- c. Otherwise, do nothing and move on to the next node.
After iterating over all the nodes in the list, return arr[1] as the second smallest element in the list.
C++
#include <bits/stdc++.h> using namespace std; struct Node { int data; Node* next; }; // Function to find the second smallest element in a linked list int findSecondSmallest(Node* head) { if (head == nullptr || head->next == nullptr) { return INT_MAX; } int arr[2] = {head->data, head->next->data}; sort(arr, arr + 2); Node* curr = head->next->next; while (curr != nullptr) { if (curr->data < arr[0]) { arr[1] = arr[0]; arr[0] = curr->data; } else if (curr->data < arr[1] && curr->data != arr[0]) { arr[1] = curr->data; } curr = curr->next; } return arr[1]; } // Driver code int main() { // Create a linked list Node* head = new Node({1, new Node({34, new Node({10, new Node({1, new Node({35, new Node({12, nullptr})})})})})}); // Find the second smallest element in the linked list int secondSmallest = findSecondSmallest(head); if (secondSmallest == INT_MAX) { cout << "There is no second smallest element in the list." << endl; } else { cout << "The second smallest element in the list is " << secondSmallest << "." << endl; } return 0; } |
Java
import java.util.Arrays; class Node { public int data; public Node next; } class Main { // Function to find the second smallest element in a // linked list public static int findSecondSmallest(Node head) { if (head == null || head.next == null ) { return Integer.MAX_VALUE; } int [] arr = { head.data, head.next.data }; Arrays.sort(arr); Node curr = head.next.next; while (curr != null ) { if (curr.data < arr[ 0 ]) { arr[ 1 ] = arr[ 0 ]; arr[ 0 ] = curr.data; } else if (curr.data < arr[ 1 ] && curr.data != arr[ 0 ]) { arr[ 1 ] = curr.data; } curr = curr.next; } return arr[ 1 ]; } // Driver code public static void main(String[] args) { // Create a linked list Node head = new Node(); head.data = 1 ; head.next = new Node(); head.next.data = 34 ; head.next.next = new Node(); head.next.next.data = 10 ; head.next.next.next = new Node(); head.next.next.next.data = 1 ; head.next.next.next.next = new Node(); head.next.next.next.next.data = 35 ; head.next.next.next.next.next = new Node(); head.next.next.next.next.next.data = 12 ; // Find the second smallest element in the linked // list int secondSmallest = findSecondSmallest(head); if (secondSmallest == Integer.MAX_VALUE) { System.out.println( "There is no second smallest element in the list." ); } else { System.out.println( "The second smallest element in the list is " + secondSmallest + "." ); } } } |
Python3
import sys class Node: def __init__( self , data): self .data = data self . next = None # Function to find the second smallest element in a linked list def findSecondSmallest(head): if head = = None or head. next = = None : return sys.maxsize arr = [head.data, head. next .data] arr.sort() curr = head. next . next while curr ! = None : if curr.data < arr[ 0 ]: arr[ 1 ] = arr[ 0 ] arr[ 0 ] = curr.data elif curr.data < arr[ 1 ] and curr.data ! = arr[ 0 ]: arr[ 1 ] = curr.data curr = curr. next return arr[ 1 ] # Driver code if __name__ = = '__main__' : # Create a linked list head = Node( 1 ) head. next = Node( 34 ) head. next . next = Node( 10 ) head. next . next . next = Node( 1 ) head. next . next . next . next = Node( 35 ) head. next . next . next . next . next = Node( 12 ) # Find the second smallest element in the linked list secondSmallest = findSecondSmallest(head) if secondSmallest = = sys.maxsize: print ( "There is no second smallest element in the list." ) else : print ( "The second smallest element in the list is {}." . format (secondSmallest)) |
C#
using System; using System.Linq; public class Node { public int data; public Node next; } public class Program { // Function to find the second smallest element in a // linked list public static int FindSecondSmallest(Node head) { if (head == null || head.next == null ) { return int .MaxValue; } int [] arr = { head.data, head.next.data }; Array.Sort(arr); Node curr = head.next.next; while (curr != null ) { if (curr.data < arr[0]) { arr[1] = arr[0]; arr[0] = curr.data; } else if (curr.data < arr[1] && curr.data != arr[0]) { arr[1] = curr.data; } curr = curr.next; } return arr[1]; } // Driver code public static void Main() { // Create a linked list Node head = new Node{ data = 1, next = new Node{ data = 34, next = new Node{ data = 10, next = new Node{ data = 1, next = new Node{ data = 35, next = new Node{ data = 12 } } } } } }; // Find the second smallest element in the linked // list int secondSmallest = FindSecondSmallest(head); if (secondSmallest == int .MaxValue) { Console.WriteLine( "There is no second smallest element in the list." ); } else { Console.WriteLine( "The second smallest element in the list is " + secondSmallest + "." ); } } } |
Javascript
// Node class class Node { constructor(data, next) { this .data = data; this .next = next; } } // Function to find the second smallest element in a linked list function findSecondSmallest(head) { if (head == null || head.next == null ) { return Number.MAX_SAFE_INTEGER; } let arr = [head.data, head.next.data]; arr.sort((a, b) => a - b); let curr = head.next.next; while (curr != null ) { if (curr.data < arr[0]) { arr[1] = arr[0]; arr[0] = curr.data; } else if (curr.data < arr[1] && curr.data != arr[0]) { arr[1] = curr.data; } curr = curr.next; } return arr[1]; } // Driver code // Create a linked list let head = new Node(1, new Node(34, new Node(10, new Node(1, new Node(35, new Node(12, null )))))); // Find the second smallest element in the linked list let secondSmallest = findSecondSmallest(head); if (secondSmallest == Number.MAX_SAFE_INTEGER) { console.log( "There is no second smallest element in the list." ); } else { console.log( "The second smallest element in the list is " + secondSmallest + "." ); } |
The second smallest element in the list is 10.
Time complexity: O(NlogN), where N is the number of nodes in the linked list.
Auxiliary Space: O(1), as constant space is used.
A Better Solution is to traverse the Linked list twice. In the first traversal find the minimum element. In the second traversal find the smallest element greater than the element obtained in the first traversal. The time complexity of this solution is O(n).
A more Efficient Solution can be to find the second smallest element in a single traversal.
Implementation:
C++
// C++ program to print second smallest // value in a linked list #include <climits> #include <iostream> using namespace std; // A linked list node struct Node { int data; struct Node* next; }; // Function to add a node at the // beginning of Linked List void push( struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } // Function to print the second // smallest element void print2smallest( struct Node* head) { int first = INT_MAX, second = INT_MAX; struct Node* temp = head; while (temp != NULL) { if (temp->data < first) { second = first; first = temp->data; } // If current node's data is in between // first and second then update second else if (temp->data < second && temp->data != first) second = temp->data; temp = temp->next; } if (second == INT_MAX) cout << "There is no second smallest element\n" ; else cout << "The second smallest element is " << second; } // Driver program to test above function int main() { struct Node* start = NULL; /* The constructed linked list is: 12 -> 35 -> 1 -> 10 -> 34 -> 1 */ push(&start, 1); push(&start, 34); push(&start, 10); push(&start, 1); push(&start, 35); push(&start, 12); print2smallest(start); return 0; } |
Java
// Java program to print second smallest // value in a linked list class GFG { // A linked list node static class Node { int data; Node next; }; // Function to add a node at the // beginning of Linked List static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return new_node; } // Function to print the second // smallest element static void print2smallest(Node head) { int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE; Node temp = head; while (temp != null ) { if (temp.data < first) { second = first; first = temp.data; } // If current node's data is in between // first and second then update second else if (temp.data < second && temp.data != first) second = temp.data; temp = temp.next; } if (second == Integer.MAX_VALUE) System.out.print( "There is no second smallest element\n" ); else System.out.print( "The second smallest element is " + second); } // Driver code public static void main(String[] args) { Node start = null ; /* The constructed linked list is: 12.35.1.10.34.1 */ start = push(start, 1 ); start = push(start, 34 ); start = push(start, 10 ); start = push(start, 1 ); start = push(start, 35 ); start = push(start, 12 ); print2smallest(start); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to print second smallest # value in a linked list # A linked list node class Node : def __init__( self ): self .data = 0 self . next = None # Function to add a node at the # beginning of Linked List def push(head_ref, new_data): new_node = Node() new_node.data = new_data new_node. next = head_ref head_ref = new_node return new_node # Function to print the second # smallest element def print2smallest(head): first = 32676 second = 32676 temp = head while (temp ! = None ): if (temp.data < first): second = first first = temp.data # If current node's data is in between # first and second then update second elif (temp.data < second and temp.data ! = first): second = temp.data temp = temp. next if (second = = 32676 ): print ( "There is no second smallest element" ) else : print ( "The second smallest element is " , second) # Driver code start = None # The constructed linked list is: # 12.35.1.10.34.1 start = push(start, 1 ) start = push(start, 34 ) start = push(start, 10 ) start = push(start, 1 ) start = push(start, 35 ) start = push(start, 12 ) print2smallest(start) # This code is contributed by Arnab Kundu |
C#
// C# program to print second smallest // value in a linked list using System; class GFG { // A linked list node class Node { public int data; public Node next; }; // Function to add a node at the // beginning of Linked List static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return new_node; } // Function to print the second // smallest element static void print2smallest(Node head) { int first = int .MaxValue, second = int .MaxValue; Node temp = head; while (temp != null ) { if (temp.data < first) { second = first; first = temp.data; } // If current node's data is in between // first and second then update second else if (temp.data < second && temp.data != first) second = temp.data; temp = temp.next; } if (second == int .MaxValue) Console.Write( "There is no second smallest element\n" ); else Console.Write( "The second smallest element is " + second); } // Driver code public static void Main(String[] args) { Node start = null ; /* The constructed linked list is: 12 -> 35 -> 1 -> 10 -> 34 -> 1 */ start = push(start, 1); start = push(start, 34); start = push(start, 10); start = push(start, 1); start = push(start, 35); start = push(start, 12); print2smallest(start); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to print second smallest // value in a linked list // Structure to represent a node of the tree class Node { constructor() { this .data = 0; this .next = null ; } } // Function to add a node at the // beginning of Linked List function push( head_ref, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return new_node; } // Function to print the second // smallest element function print2smallest( head) { let first = Number.MAX_VALUE , second = Number.MAX_VALUE ; var temp = head; while (temp != null ) { if (temp.data < first) { second = first; first = temp.data; } // If current node's data is in between // first and second then update second else if (temp.data < second && temp.data != first) second = temp.data; temp = temp.next; } if (second == Number.MAX_VALUE ) document.write( "There is no second smallest element" + "</br>" ); else document.write( "The second smallest element is " + second); } // Driver Code var start = null ; /* The constructed linked list is: 12.35.1.10.34.1 */ start = push(start, 1); start = push(start, 34); start = push(start, 10); start = push(start, 1); start = push(start, 35); start = push(start, 12); print2smallest(start); // This code is contributed by jana_sayantan. </script> |
The second smallest element is 10
Time complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(1), as constant space is used.
Approach:(Using a Priority Queue)
- Create a priority queue (min-heap).
- Traverse the linked list and insert all elements into the priority queue.
- Remove the smallest element from the priority queue.
- The next element in the priority queue will be the second smallest element.
- Extract the smallest element from the priority queue using pq.top() and pq.pop(). Assign this smallest element to a variable smallest.
- Iterate over the remaining elements in the priority queue using a while loop while (!pq.empty()) and Inside the loop, extract the current element from the priority queue using pq.top() and pq.pop(), and assign it to a variable current.
- Check if the current element is not equal to smallest. If it’s not equal, then it means we have found the second smallest element. Return the current element. If the loop completes without finding a second smallest element, return INT_MAX to indicate that there is no second smallest element.
- Finally, in the main() function, create the linked list and call the findSecondSmallest() function to get the second smallest element. Print the result accordingly.
Below is the implementation of above approach.
C++
#include <bits/stdc++.h> using namespace std; struct Node { int data; Node* next; }; // Function to find the second smallest element in a linked list int findSecondSmallest(Node* head) { if (head == nullptr || head->next == nullptr) { return INT_MAX; } priority_queue< int , vector< int >, greater< int >> pq; // Min-Heap Node* curr = head; while (curr != nullptr) { pq.push(curr->data); curr = curr->next; } int smallest = pq.top(); pq.pop(); while (!pq.empty()) { int current = pq.top(); pq.pop(); if (current != smallest) { return current; } } return INT_MAX; } // Driver code int main() { // Create a linked list Node* head = new Node({1, new Node({34, new Node({10, new Node({1, new Node({35, new Node({12, nullptr})})})})})}); // Find the second smallest element in the linked list int secondSmallest = findSecondSmallest(head); if (secondSmallest == INT_MAX) { cout << "There is no second smallest element in the list." << endl; } else { cout << "The second smallest element in the list is " << secondSmallest << "." << endl; } return 0; } |
Java
import java.util.PriorityQueue; class Node { int data; Node next; Node( int data) { this .data = data; this .next = null ; } } public class Main { // Function to find the second smallest element in a // linked list public static int findSecondSmallest(Node head) { if (head == null || head.next == null ) { return Integer.MAX_VALUE; } PriorityQueue<Integer> minHeap = new PriorityQueue<>(); Node current = head; while (current != null ) { minHeap.offer(current.data); current = current.next; } int smallest = minHeap.poll(); while (!minHeap.isEmpty()) { int nextValue = minHeap.poll(); if (nextValue != smallest) { return nextValue; } } return Integer.MAX_VALUE; } // Driver code public static void main(String[] args) { // Create a linked list Node head = new Node( 1 ); head.next = new Node( 34 ); head.next.next = new Node( 10 ); head.next.next.next = new Node( 1 ); head.next.next.next.next = new Node( 35 ); head.next.next.next.next.next = new Node( 12 ); // Find the second smallest element in the linked // list int secondSmallest = findSecondSmallest(head); if (secondSmallest == Integer.MAX_VALUE) { System.out.println( "There is no second smallest element in the list." ); } else { System.out.println( "The second smallest element in the list is " + secondSmallest + "." ); } } } |
Python3
import heapq # Define a Node class for the linked list class Node: def __init__( self , data): self .data = data self . next = None # Function to find the second smallest element in a linked list def find_second_smallest(head): if head is None or head. next is None : return float ( 'inf' ) min_heap = [] # Min-Heap using heapq module curr = head while curr is not None : heapq.heappush(min_heap, curr.data) curr = curr. next smallest = heapq.heappop(min_heap) while min_heap: current = heapq.heappop(min_heap) if current ! = smallest: return current return float ( 'inf' ) # Driver code if __name__ = = "__main__" : # Create a linked list head = Node( 1 ) head. next = Node( 34 ) head. next . next = Node( 10 ) head. next . next . next = Node( 1 ) head. next . next . next . next = Node( 35 ) head. next . next . next . next . next = Node( 12 ) # Find the second smallest element in the linked list second_smallest = find_second_smallest(head) if second_smallest = = float ( 'inf' ): print ( "There is no second smallest element in the list." ) else : print (f "The second smallest element in the list is {second_smallest}." ) |
C#
using System; using System.Collections.Generic; class Node { public int data; public Node next; } class Program { // Function to find the second smallest element in a // linked list static int FindSecondSmallest(Node head) { if (head == null || head.next == null ) { return int .MaxValue; } var pq = new PriorityQueue< int >(); // Custom PriorityQueue class Node curr = head; while (curr != null ) { pq.Enqueue(curr.data); curr = curr.next; } int smallest = pq.Dequeue(); while (pq.Count > 0) { int current = pq.Dequeue(); if (current != smallest) { return current; } } return int .MaxValue; } // PriorityQueue implementation public class PriorityQueue<T> where T : IComparable<T> { private List<T> data; public PriorityQueue() { data = new List<T>(); } public void Enqueue(T item) { data.Add(item); int childIndex = data.Count - 1; while (childIndex > 0) { int parentIndex = (childIndex - 1) / 2; if (data[childIndex].CompareTo( data[parentIndex]) >= 0) break ; T tmp = data[childIndex]; data[childIndex] = data[parentIndex]; data[parentIndex] = tmp; childIndex = parentIndex; } } public T Dequeue() { int lastIndex = data.Count - 1; T frontItem = data[0]; data[0] = data[lastIndex]; data.RemoveAt(lastIndex); lastIndex--; int parentIndex = 0; while ( true ) { int leftChildIndex = parentIndex * 2 + 1; if (leftChildIndex > lastIndex) break ; int rightChildIndex = parentIndex * 2 + 2; int minIndex = leftChildIndex; if (rightChildIndex <= lastIndex && data[rightChildIndex].CompareTo( data[leftChildIndex]) < 0) { minIndex = rightChildIndex; } if (data[parentIndex].CompareTo( data[minIndex]) <= 0) break ; T tmp = data[parentIndex]; data[parentIndex] = data[minIndex]; data[minIndex] = tmp; parentIndex = minIndex; } return frontItem; } public int Count { get { return data.Count; } } } // Driver code static void Main( string [] args) { // Create a linked list Node head = new Node{ data = 1, next = new Node{ data = 34, next = new Node{ data = 10, next = new Node{ data = 1, next = new Node{ data = 35, next = new Node{ data = 12, next = null } } } } } }; // Find the second smallest element in the linked // list int secondSmallest = FindSecondSmallest(head); if (secondSmallest == int .MaxValue) { Console.WriteLine( "There is no second smallest element in the list." ); } else { Console.WriteLine( "The second smallest element in the list is " + secondSmallest + "." ); } } } |
Javascript
class Node { constructor(data) { this .data = data; this .next = null ; } } // Function to find the second smallest element in // linked list function GFG(head) { if (head === null || head.next === null ) { return Infinity; // Return positive infinity if the list is empty or has only one element } const pq = []; // Min-Heap implemented as an array let curr = head; while (curr !== null ) { pq.push(curr.data); curr = curr.next; } pq.sort((a, b) => a - b); // Sort the elements in ascending order let smallest = pq[0]; let secondSmallest = Infinity; for (let i = 1; i < pq.length; i++) { if (pq[i] !== smallest) { secondSmallest = pq[i]; break ; } } return secondSmallest !== Infinity ? secondSmallest : Infinity; } // Driver code function main() { // Create a linked list const head = new Node(1); head.next = new Node(34); head.next.next = new Node(10); head.next.next.next = new Node(1); head.next.next.next.next = new Node(35); head.next.next.next.next.next = new Node(12); // Find the second smallest element in the linked list const secondSmallest = GFG(head); if (secondSmallest === Infinity) { console.log( "There is no second smallest element in the list." ); } else { console.log( "The second smallest element in the list is " + secondSmallest + "." ); } } main(); |
The second smallest element in the list is 10.
Time Complexity: The time complexity is O(n log n), where n is the number of elements in the linked list. This is because inserting elements into the priority queue takes O(n) time, and extracting elements takes O((n-1) log n) time. Overall, the code has a time complexity of O(n log n).
Auxiliary Space: The auxiliary space complexity is O(n). This is because the priority queue requires space to store all the elements in the worst case, resulting in O(n) space usage. Other variables in the code require constant space, which can be considered O(1). Therefore, the overall auxiliary space complexity is O(n).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!