Find smallest and largest elements in singly linked list
Given a singly linked list of n nodes and find the smallest and largest elements in linked list.
Examples:
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
The idea is to traverse the linked list while head not equal to NULL and initialise the max and min variable to INT_MIN and INT_MAX respectively. After that check a condition that if max value is less then head value is assigned to max or min value is greater then head value is assigned to min otherwise head point to next node. Continue this process until head not equal to NULL.
C++
|
// C++ Program to find smallest and largest // elements in singly linked list. #include <bits/stdc++.h>
using namespace std; /* Linked list node */ struct Node { int data; struct Node* next; };
// Function that returns the largest element // from the linked list. int largestElement(struct Node* head) { // Declare a max variable and initialize // it with INT_MIN value. // INT_MIN is integer type and its value // is -32767 or less. int max = INT_MIN;
// Check loop while head not equal to NULL while (head != NULL) {
// If max is less then head->data then // assign value of head->data to max // otherwise node point to next node. if (max < head->data) max = head->data; head = head->next; } return max; }
// Function that returns smallest element // from the linked list. int smallestElement(struct Node* head) { // Declare a min variable and initialize // it with INT_MAX value. // INT_MAX is integer type and its value // is 32767 or greater. int min = INT_MAX;
// Check loop while head not equal to NULL while (head != NULL) {
// If min is greater then head->data then // assign value of head->data to min // otherwise node point to next node. if (min > head->data) min = head->data;
head = head->next; } return min; }
// Function that push the element in linked list. void push(struct Node** head, int data) { // Allocate dynamic memory for newNode. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// Assign the data into newNode. newNode->data = data;
// newNode->next assign the address of // head node. newNode->next = (*head);
// newNode become the headNode. (*head) = newNode; }
// Display linked list. void printList(struct Node* head) { while (head != NULL) { printf("%d -> ", head->data); head = head->next; } cout << "NULL" << endl; }
// Driver program to test the functions int main() { // Start with empty list struct Node* head = NULL;
// Using push() function to construct // singly linked list // 17->22->13->14->15 push(&head, 15); push(&head, 14); push(&head, 13); push(&head, 22); push(&head, 17); cout << "Linked list is : " << endl;
// Call printList() function to display // the linked list. printList(head); cout << "Maximum element in linked list:";
// Call largestElement() function to get largest // element in linked list. cout << largestElement(head) << endl; cout << "Minimum element in linked list:";
// Call smallestElement() function to get smallest // element in linked list. cout << smallestElement(head) << endl;
return 0; } |
Java
|
// Java program to find smallest and largest // elements in singly linked list. class GfG {
/* Linked list node */ static class Node { int data; Node next; } static Node head = null;
// Function that returns the largest element // from the linked list. static int largestElement(Node head) {
// Declare a max variable and initialize // it with INT_MIN value. // INT_MIN is integer type and its value // is -32767 or less. int max = Integer.MIN_VALUE;
// Check loop while head not equal to NULL while (head != null) {
// If max is less then head->data then // assign value of head->data to max // otherwise node point to next node. if (max < head.data) max = head.data; head = head.next; } return max; }
// Function that returns smallest element // from the linked list. static int smallestElement(Node head) {
// Declare a min variable and initialize // it with INT_MAX value. // INT_MAX is integer type and its value // is 32767 or greater. int min = Integer.MAX_VALUE;
// Check loop while head not equal to NULL while (head != null) {
// If min is greater then head->data then // assign value of head->data to min // otherwise node point to next node. if (min > head.data) min = head.data;
head = head.next; } return min; }
// Function that push the element in linked list. static void push(int data) { // Allocate dynamic memory for newNode. Node newNode = new Node();
// Assign the data into newNode. newNode.data = data;
// newNode->next assign the address of // head node. newNode.next = (head);
// newNode become the headNode. (head) = newNode; }
// Display linked list. static void printList(Node head) { while (head != null) { System.out.print(head.data + " -> "); head = head.next; } System.out.println("NULL"); }
// Driver code public static void main(String[] args) { // Start with empty list // head = new Node();
// Using push() function to construct // singly linked list // 17->22->13->14->15 push( 15); push( 14); push( 13); push( 22); push( 17); System.out.println("Linked list is : ") ;
// Call printList() function to // display the linked list. printList(head); System.out.print("Maximum element in linked list: ");
// Call largestElement() function to get // largest element in linked list. System.out.println(largestElement(head)); System.out.print("Minimum element in linked list: ");
// Call smallestElement() function to get // smallest element in linked list. System.out.print(smallestElement(head)); } }
// This code is contributed by Prerna saini. |
Python
|
# Python3 program to find smallest and largest # elements in singly linked list.
# Linked list node class Node:
def __init__(self): self.data = None self.next = None
head = None
# Function that returns the largest element # from the linked list. def largestElement(head):
# Declare a max variable and initialize # it with INT_MIN value. # INT_MIN is integer type and its value # is -32767 or less. max = -32767
# Check loop while head not equal to None while (head != None):
# If max is less then head.data then # assign value of head.data to max # otherwise node point to next node. if (max < head.data) : max = head.data head = head.next
return max
# Function that returns smallest element # from the linked list. def smallestElement(head):
# Declare a min variable and initialize # it with INT_MAX value. # INT_MAX is integer type and its value # is 32767 or greater. min = 32767
# Check loop while head not equal to None while (head != None) :
# If min is greater then head.data then # assign value of head.data to min # otherwise node point to next node. if (min > head.data) : min = head.data head = head.next
return min
# Function that push the element in linked list. def push( data) :
global head
# Allocate dynamic memory for newNode. newNode = Node()
# Assign the data into newNode. newNode.data = data
# newNode.next assign the address of # head node. newNode.next = (head)
# newNode become the headNode. (head) = newNode
# Display linked list. def printList( head) :
while (head != None) : print(head.data ,end= " -> ") head = head.next
print("None")
# Driver code
# Start with empty list # head = new Node()
# Using push() function to construct # singly linked list # 17.22.13.14.15 push( 15) push( 14) push( 13) push( 22) push( 17) print("Linked list is : ")
# Call printList() function to # display the linked list. printList(head) print("Maximum element in linked list: ",end="")
# Call largestElement() function to get # largest element in linked list. print(largestElement(head)) print("Minimum element in linked list: ",end="")
# Call smallestElement() function to get # smallest element in linked list. print(smallestElement(head),end="")
# This code is contributed by Arnab Kundu |
C#
|
// C# program to find smallest and largest // elements in singly linked list. using System;
class GfG {
/* Linked list node */ class Node { public int data; public Node next; } static Node head = null;
// Function that returns the largest element // from the linked list. static int largestElement(Node head) {
// Declare a max variable and initialize // it with INT_MIN value. // INT_MIN is integer type and its value // is -32767 or less. int max = int.MinValue;
// Check loop while head not equal to NULL while (head != null) {
// If max is less then head->data then // assign value of head->data to max // otherwise node point to next node. if (max < head.data) max = head.data; head = head.next; } return max; }
// Function that returns smallest element // from the linked list. static int smallestElement(Node head) {
// Declare a min variable and initialize // it with INT_MAX value. // INT_MAX is integer type and its value // is 32767 or greater. int min = int.MaxValue;
// Check loop while head not equal to NULL while (head != null) {
// If min is greater then head->data then // assign value of head->data to min // otherwise node point to next node. if (min > head.data) min = head.data;
head = head.next; } return min; }
// Function that push the element in linked list. static void push(int data) { // Allocate dynamic memory for newNode. Node newNode = new Node();
// Assign the data into newNode. newNode.data = data;
// newNode->next assign the address of // head node. newNode.next = (head);
// newNode become the headNode. (head) = newNode; }
// Display linked list. static void printList(Node head) { while (head != null) { Console.Write(head.data + " -> "); head = head.next; } Console.WriteLine("NULL"); }
// Driver code public static void Main() { // Start with empty list // head = new Node();
// Using push() function to construct // singly linked list // 17->22->13->14->15 push( 15); push( 14); push( 13); push( 22); push( 17); Console.WriteLine("Linked list is : ") ;
// Call printList() function to // display the linked list. printList(head); Console.Write("Maximum element in linked list: ");
// Call largestElement() function to get // largest element in linked list. Console.WriteLine(largestElement(head)); Console.Write("Minimum element in linked list: ");
// Call smallestElement() function to get // smallest element in linked list. Console.Write(smallestElement(head)); } }
// This code is contributed by PrinciRaj1992 |
Javascript
|
<script>
// JavaScript program to find smallest and largest // elements in singly linked list. /* Linked list node */ class Node { constructor(val) { this.data = val; this.next = null; } } var head = null;
// Function that returns the largest element // from the linked list. function largestElement(head) {
// Declare a max variable and initialize // it with INT_MIN value. // INT_MIN is integer type and its value // is -32767 or less. var max = Number.MIN_VALUE;
// Check loop while head not equal to NULL while (head != null) {
// If max is less then head->data then // assign value of head->data to max // otherwise node point to next node. if (max < head.data) max = head.data; head = head.next; } return max; }
// Function that returns smallest element // from the linked list. function smallestElement(head) {
// Declare a min variable and initialize // it with INT_MAX value. // INT_MAX is integer type and its value // is 32767 or greater. var min = Number.MAX_VALUE;
// Check loop while head not equal to NULL while (head != null) {
// If min is greater then head->data then // assign value of head->data to min // otherwise node point to next node. if (min > head.data) min = head.data;
head = head.next; } return min; }
// Function that push the element in linked list. function push(data) { // Allocate dynamic memory for newNode. var newNode = new Node();
// Assign the data into newNode. newNode.data = data;
// newNode->next assign the address of // head node. newNode.next = (head);
// newNode become the headNode. (head) = newNode; }
// Display linked list. function printList(head) { while (head != null) { document.write(head.data + " -> "); head = head.next; } document.write("NULL"); }
// Driver code
// Start with empty list // head = new Node();
// Using push() function to construct // singly linked list // 17->22->13->14->15 push(15); push(14); push(13); push(22); push(17); document.write("Linked list is : <br/>");
// Call printList() function to // display the linked list. printList(head); document.write("<br/>Maximum element in linked list: ");
// Call largestElement() function to get // largest element in linked list. document.write(largestElement(head)); document.write("<br/>Minimum element in linked list: ");
// Call smallestElement() function to get // smallest element in linked list. document.write(smallestElement(head));
// This code contributed by Rajput-Ji
</script> |
Output:
Linked list is : 17 -> 22 -> 13 -> 14 -> 15 -> NULL Maximum element in linked list: 22 Minimum element in linked list: 13This article is contributed by Dharmendra kumar. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Article Tags :
Linked List
Practice Tags :
Linked List
Read Full Article
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
The idea is to traverse the linked list while head not equal to NULL and initialise the max and min variable to INT_MIN and INT_MAX respectively. After that check a condition that if max value is less then head value then head value is assign to max or min value is greater then head value then head value is assign to min otherwise head point to next node. Continue this process until head not equal to NULL.
Program to find the maximum and minimum value node from a singly linked list
Explanation
In this program, we need to find out the minimum and maximum value node in the given singly linked list.
We will maintain two variables min and max. Min will hold minimum value node, and max will hold maximum value node. In the above example, 1 will be minimum value node and 8 will be maximum value node. The algorithm to find the maximum and minimum node is given below.
Algorithm
- Create a class Node which has two attributes: data and next. Next is a pointer to the next node in the list.
- Create another class MinMax which has two attributes: head and tail.
- addNode() will add a new node to the list:
- Create a new node.
- It first checks, whether the head is equal to null which means the list is empty.
- If the list is empty, both head and tail will point to a newly added node.
- If the list is not empty, the new node will be added to end of the list such that tail's next will point to a newly added node. This new node will become the new tail of the list.
- minNode() will display minimum value node:
- Define a variable min and initialize it with head's data.
- Node current will point to head.
- Iterate through the list by comparing each node's data with min.
- If min is greater than current's data then, min will hold current's data.
- At the end of the list, variable min will hold minimum value node.
- Display the min value.
- maxNode() will display maximum value node:
- Define a variable max and initialize it with head's data.
- Node current will point to head.
- Iterate through the list by comparing each node's data with max.
- If max is less than current's data then, max will hold current's data.
- At the end of the list, variable max will hold maximum value node.
- Display the max value.
Solution
Python
Output:
Minimum value node in the list: 1 Maximum value node in the list: 8
C
Output:
Minimum value node in the list: 1 Maximum value node in the list: 8
JAVA
Output:
Minimum value node in the list: 1 Maximum value node in the list: 8
C#
Output:
Minimum value node in the list: 1 Maximum value node in the list: 8
PHP
Output:
Minimum value node in the list: 1 Maximum value node in the list: 8
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 : 1We 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 : 2We 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.
- 1) Find the second smallest element of linked list in java 2) Find the second smallest element of linked list in c++ 3) Find the second smallest element of linked list in c 4) Find the second smallest element of linked list in c# 5) Find the second smallest element of linked list in php 6) Find the second smallest element of linked list in python 7) Find the second smallest element of linked list in ruby 8) Find the second smallest element of linked list in scala 9) Find the second smallest element of linked list in swift 10) Find the second smallest element of linked list in kotlin 11) Find the second smallest element of linked list in node js 12) Find the second smallest element of linked list in vb.net 13) Find the second smallest element of linked list in golang 14) Find the second smallest element of linked list in typescript