Ở đây chúng ta sẽ xem cách lấy giá trị nhỏ nhất và lớn nhất từ một danh sách tuyến tính liên kết đơn lẻ. Khái niệm cơ bản là rất đơn giản. Phần tiếp theo của nút cuối cùng sẽ được trỏ đến nút đầu tiên, nút đầu tiên cũng sẽ được trỏ bằng cách sử dụng con trỏ bắt đầu. Khi chúng ta chèn phần tử nào đó vào danh sách, sau khi chèn phần tiếp theo của nút mới được chèn sẽ được cập nhật địa chỉ của nút bắt đầu.
Ban đầu, min được gán với dương vô cùng và max được gán với vô cùng âm. Bây giờ lướt qua danh sách từ trái sang phải. Nếu phần tử hiện tại nhỏ hơn phần tử min thì hãy cập nhật giá trị min, nếu phần tử hiện tại lớn hơn phần tử max thì hãy cập nhật giá trị max. Do đó, chúng tôi có thể nhận được các giá trị tối thiểu và tối đa.
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);
} Đầu ra
99 11 22 10 44 55 66 Minimum: 10, Maximum: 99