Find the smallest and largest elements in a singly linked list

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given a singly linked list. We have to find the smallest and the largest element of the linked list.

Problem Statement Understanding

Let’s try to understand the problem with help of example.

Suppose the linked list is:

In this list, the smallest element is 2 and the largest element is 9. So, the final output will be:

• Maximum Element: 9
• Minimum Element: 2

Input :

Output : Maximum Element: 9, Minimum Element: 2.

Explanation: As the maximum element is 9 and the minimum element is 2, we are printing 9 and 2.

This question is not a tricky one. We just have to make use of simple list traversal to solve this problem. Let us have a glance at the approach.

Approach

The approach is going to be simple.

• We will create two variables min and max.

• min will be initialized with INT_MAX and max will be initialized with INT_MIN.

• We are using INT_MAX because all the integers are lesser than it, and INT_MIN because all the integers are greater than it. With the help of these, finding the minimum and maximum becomes easy.

• Now, we will traverse through the given list, and for every node, we will have two checks.
  1) If the data of the current node is less than the data of min, we will store the current node’s data in min.
  2) Else, If the data of the current node is greater than max, we will store the current node’s data in max.

• After reaching the end of the list, min and max will contain the smallest and the largest element, respectively.

Algorithm (Largest element)

• Create a variable max and initialize it with INT_MIN.
• Traverse through the list and for every node, compare its data with max.
• If the current node’s data is greater than max, then store the value of the current node’s data in max.
• In the end, max will contain the largest element of the list.

Algorithm (Smallest element)

• Create a variable min and initialize it with INT_MAX.
• Traverse through the list and for every node, compare its data with min.
• If the current node’s data is lesser than min, then store the value of the current node’s data in min.
• In the end, min will contain the largest element of the list.

Dry Run

Finding Maximum Element

Finding Minimum Element

Code Implementation

#include 

using namespace std;

struct Node {
    int data;
    struct Node* next;
};

int largestElement(struct Node* head)
{

    int max = INT_MIN;

    while (head != NULL) {

        if (max < head->data)
            max = head->data;
        head = head->next;
    }
    return max;
}

int smallestElement(struct Node* head)
{

    int min = INT_MAX;


    while (head != NULL) {

        if (min > head->data)
            min = head->data;

        head = head->next;
    }
    return min;
}

void push(struct Node** head, int data)
{

    struct Node* newNode =
        (struct Node*)malloc(sizeof(struct Node));

    newNode->data = data;

    newNode->next = (*head);

    (*head) = newNode;
}

// Display linked list.
void printList(struct Node* head)
{
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main()
{
    struct Node* head = NULL;
    push(&head, 9);
    push(&head, 7);
    push(&head, 2);
    push(&head, 5);
    
    cout << "Linked list is: " << endl;

    printList(head);
    cout << "Maximum element in linked list: ";

    cout << largestElement(head) << endl;
    cout << "Minimum element in linked list: ";

    cout << smallestElement(head) << endl;

    return 0;
}

public class PrepBytes
{

static class Node
{
    int data;
    Node next;
}
static Node head = null;

static int largestElement(Node head)
{
    
    int max = Integer.MIN_VALUE;

    while (head != null)
    {

        if (max < head.data)
            max = head.data;
        head = head.next;
    }
    return max;
}

static int smallestElement(Node head)
{

    int min = Integer.MAX_VALUE;

    while (head != null)
    {

        if (min > head.data)
            min = head.data;

        head = head.next;
    }
    return min;
}

static void push(int data)
{

    Node newNode = new Node();

    newNode.data = data;

    newNode.next = (head);

    (head) = newNode;
}

static void printList(Node head)
{
    while (head != null) {
        System.out.print(head.data + " -> ");
        head = head.next;
    }
    System.out.println("NULL");
}


public static void main(String[] args)
{
    push( 9);
    push( 7);
    push( 2);
    push( 5);
    System.out.println("Linked list is: ") ;
    printList(head);
    System.out.print("Maximum element in linked list: ");
    System.out.println(largestElement(head));
    System.out.print("Minimum element in linked list: ");
    System.out.print(smallestElement(head));
}
}

Output

Linked list is:
5 -> 2 -> 7 -> 9 -> NULL
Maximum element in linked list: 9
Minimum element in linked list: 2

Time Complexity: O(n), as list traversal is needed.

So, in this article, we have tried to explain the most efficient approach to find the smallest and the largest element in a singly linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.