Skip to main content

Find minimum and maximum elements in Circular Linked List

A circular linked list is a type of linked list where the last node points back to the first node, creating a circular structure. Each node in the list contains data and a reference (or "next" pointer) to the next node in the sequence. The problem at hand is to find the minimum and maximum elements within a given circular linked list.

Problem Statement

Given a circular linked list, we need to develop a program that finds and outputs the minimum and maximum elements present in the list.

Example

Let's consider a circular linked list with the following nodes: 31 -> 15 -> 59 -> 45 -> 14 -> 58 -> 49 -> 57 -> 31

In this example, the minimum element is 14, and the maximum element is 59.

Idea to Solve the Problem

find min and max value in circular linked list

To find the minimum and maximum elements in a circular linked list, we can traverse the list while keeping track of the current minimum and maximum values encountered. We initialize the minimum and maximum with the data from the first node, and then iterate through the rest of the nodes, updating the minimum and maximum values whenever a smaller or larger element is encountered.

Pseudocode

findMinAndMax(CircularLinkedList me):
    if me.head is null:
        print "Empty linked list"
        return
    initialize min = me.head
    initialize max = me.head
    initialize temp = me.head.next
    while temp is not null and temp is not equal to me.head:
        if min.data > temp.data:
            min = temp
        if max.data < temp.data:
            max = temp
        move temp to the next node
    print "Min:", min.data
    print "Max:", max.data

Algorithm Explanation

  1. Check if the circular linked list is empty. If it is, print "Empty linked list" and return.
  2. Initialize variables min and max with the data from the first node (me.head).
  3. Start traversing from the second node (temp = me.head.next).
  4. While the current node (temp) is not null and not equal to the starting node (me.head), compare its data with the current min and max.
  5. If the data of temp is smaller than the data of min, update min to temp.
  6. If the data of temp is larger than the data of max, update max to temp.
  7. Move temp to the next node.
  8. After traversing the entire circular linked list, print the minimum and maximum values.

Code Solution

Resultant Output Explanation

In the provided code, a circular linked list is created and populated with nodes containing values 31, 15, 59, 45, 14, 58, 49, and 57. The findMinAndMax() function is called, which calculates and outputs the minimum (14) and maximum (59) values within the circular linked list.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the circular linked list. We traverse the entire list once to find the minimum and maximum values.





Comment

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