Linked list (danh sách liên kết) là cấu trúc dữ liệu tuyến tính nơi các phần tử được liên kết qua con trỏ. Mỗi node có phần dữ liệu (data) và con trỏ next trỏ đến node tiếp theo.
Cho một singly linked list và một số K. Nhiệm vụ: tìm phần tử lớn nhất và nhỏ nhất trong linked list mà chia hết cho K.
Ví dụ 1
Input
SList: 5 → 2 → 10 → 12 → 3 → 20 → 7, K = 5
Output
Maximum element divisible by K: 20 Minimum element divisible by K: 5
Giải thích: Các số chia hết cho 5: 5, 10, 20. Min = 5, Max = 20.
Ví dụ 2
Input
SList: 12 → 2 → 5 → 18 → 3 → 144 → 7, K = 4
Output
Maximum element divisible by K: 144 Minimum element divisible by K: 12
Thuật toán
- Tạo cấu trúc node cho linked list.
- Tạo linked list và thêm các phần tử.
- Duyệt linked list từ head.
- Với mỗi node, kiểm tra
data % K == 0. - Cập nhật maxD và minD nếu thỏa mãn.
- In kết quả.
Ví dụ code hoàn chỉnh
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
void findDivisible(Node* head, int K) {
int maxD = INT_MIN;
int minD = INT_MAX;
bool found = false;
Node* curr = head;
while (curr != nullptr) {
if (curr->data % K == 0) {
found = true;
maxD = max(maxD, curr->data);
minD = min(minD, curr->data);
}
curr = curr->next;
}
if (found) {
cout << "Max Element divisible by K: " << maxD << endl;
cout << "Min Element divisible by K: " << minD << endl;
} else {
cout << "No element divisible by " << K << endl;
}
}
int main() {
// Tạo list: 50 → 21 → 32 → 45 → 11 → 23 → 90 → 56
Node* head = new Node(56);
head = new Node(90, head);
head = new Node(23, head);
head = new Node(11, head);
head = new Node(45, head);
head = new Node(32, head);
head = new Node(21, head);
head = new Node(50, head);
int K = 5;
findDivisible(head, K);
// Giải phóng bộ nhớ (bỏ qua cho ngắn gọn)
return 0;
}
Kết quả
Max Element divisible by K: 90 Min Element divisible by K: 45
Lưu ý: Code trên dùng C++ hiện đại (struct Node có constructor). Code gốc dùng class và con trỏ thô, dễ gây rò rỉ bộ nhớ. Phiên bản này an toàn và dễ hiểu hơn.