Tìm min và max trong danh sách liên kết đơn vòng trong C++

Chúng ta sẽ tìm giá trị nhỏ nhất và lớn nhất trong một danh sách liên kết đơn vòng (singly circular linked list). Khái niệm cơ bản: con trỏ next của nút cuối trỏ về nút đầu, nút đầu được trỏ bởi con trỏ start. Khi chèn phần tử mới, next của nút mới được cập nhật trỏ về start.

Khởi tạo min = +∞, max = -∞. Duyệt danh sách từ trái sang phải: nếu phần tử hiện tại < min thì cập nhật min, nếu > max thì cập nhật max.

Ví dụ

#include<iostream>
using namespace std;

class Node{
public:
    int data;
    Node *next;
};

Node* getNode(int key){
    Node *newNode = new Node();
    newNode->data = key;
    newNode->next = NULL;
    return newNode;
}

void insert(Node **start, int data){
    Node *current = *start;
    Node *newNode = getNode(data);
    if(*start == NULL){
        newNode->next = newNode;
        *start = newNode;
        return;
    }
    while (current->next != *start) {
        current = current->next;
    }
    newNode->next = *start;
    current->next = newNode;
}

void displayList(Node *start){
    Node* current = start;
    if (start == NULL) {
        cout << "Display List is empty";
        return;
    } else {
        do {
            cout << current->data << " ";
            current = current->next;
        } while (current != start);
    }
    cout << endl;
}

void getMinMax(Node **start){
    if(*start == NULL){
        return;
    }
    Node* current;
    current = *start;
    int min = INT_MAX, max = INT_MIN;
    while (current->next != *start) {
        if (current->data < min) {
            min = current->data;
        }
        if (current->data > max) {
            max = current->data;
        }
        current = current->next;
    }
    cout << "Minimum: " << min << ", Maximum: " << max;
}

int main() {
    int data[] = {99, 11, 22, 10, 44, 55, 66};
    int n = sizeof(data)/sizeof(data[0]);
    Node *start = NULL;
    for(int i = 0; i<n; i++){
        insert(&start, data[i]);
    }
    displayList(start);
    getMinMax(&start);
}

Kết quả

99 11 22 10 44 55 66 Minimum: 10, Maximum: 99