หาค่าสูงสุดและต่ำสุดใน Linked List ที่หารด้วย K ลงตัวใน C++

Linked List เป็นโครงสร้างข้อมูลแบบเชิงเส้นที่องค์ประกอบเชื่อมต่อกันผ่านพอยน์เตอร์ แต่ละโหนด (node) มีส่วนข้อมูล (data) และลิงก์/พอยน์เตอร์ไปยังโหนดถัดไป ข้อมูลอาจจัดเก็บในหน่วยความจำที่ไม่ติดกัน

ได้รับ singly linked list ที่มีส่วนข้อมูลและลิงก์ไปโหนดถัดไป รวมถึงจำนวน K งานคือหาค่าสูงสุด (Max) และต่ำสุด (Min) ใน linked list ที่หารด้วย K ลงตัว เนื่องจากเป็น singly linked list จึงเดินได้เพียงทิศทางเดียว ที่แต่ละโหนดจะตรวจสอบว่าข้อมูลหารด้วย K ลงตัวหรือไม่ หากใช่ และเป็นค่าสูงสุด/ต่ำสุดที่เจอมาจนถึงตอนนั้น ให้อัปเดตค่า MaxD และ MinD

ตัวอย่าง

ตัวอย่างที่ 1

Input: SList: 5→2→10→12→3→20→7, K=5

Output:

Max divisible by K: 20
Min divisible by K: 5

คำอธิบาย: ค่าที่หาร 5 ลงตัวคือ 5, 10, 20 → Min=5, Max=20

ตัวอย่างที่ 2

Input: SList: 12→2→5→18→3→144→7, K=4

Output:

Max divisible by K: 144
Min divisible by K: 12

แนวทางแก้ปัญหา

1. สร้างโครงสร้างโหนด (Node) มี data และ next pointer
2. สร้าง Linked List class มี head pointer และเมธอด addToHead()
3. สร้าง linked list โดยเรียก addToHead()
4. ฟังก์ชัน findDivisibleMinMax(head, K) รับ head และ K
5. ในฟังก์ชัน: ตั้ง maxD = INT_MIN, minD = INT_MAX
6. เดินผ่านทุกโหนดจาก head จนถึง NULL
7. ถ้า node->data % K == 0 ให้อัปเดต maxD และ minD
8. หลังลูปจบ ถ้า maxD == INT_MIN แสดงว่าไม่มีค่าหารลงตัว

ตัวอย่างโค้ด (สมัยใหม่ ใช้ struct และ smart pointers)

#include <iostream>
#include <climits>
#include <memory>
using namespace std;

struct Node {
    int data;
    unique_ptr<Node> next;
    Node(int val) : data(val), next(nullptr) {}
};

void findDivisibleMinMax(Node* head, int K) {
    int maxD = INT_MIN;
    int minD = INT_MAX;
    bool found = false;
    
    for (Node* curr = head; curr != nullptr; curr = curr->next.get()) {
        if (curr->data % K == 0) {
            found = true;
            if (curr->data > maxD) maxD = curr->data;
            if (curr->data < minD) minD = curr->data;
        }
    }
    
    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() {
    // สร้าง list: 50→21→32→45→11→23→90→56 (เพิ่มที่ head ดังนั้นลำดับจะกลับ)
    auto head = make_unique<Node>(56);
    head->next = make_unique<Node>(90);
    head->next->next = make_unique<Node>(23);
    head->next->next->next = make_unique<Node>(11);
    head->next->next->next->next = make_unique<Node>(45);
    head->next->next->next->next->next = make_unique<Node>(32);
    head->next->next->next->next->next->next = make_unique<Node>(21);
    head->next->next->next->next->next->next->next = make_unique<Node>(50);
    
    int K = 5;
    findDivisibleMinMax(head.get(), K);
    return 0;
}

ผลลัพธ์

Max Element divisible by K: 90
Min Element divisible by K: 45

โค้ดแบบคลาสสิก (ตามต้นฉบับ แต่แก้ไขให้ compile ได้)

#include <iostream>
#include <climits>
using namespace std;

class SLLnode {
public:
    int info;
    SLLnode* next;
    SLLnode(int e, SLLnode* ptr = nullptr) : info(e), next(ptr) {}
};

class SLList {
public:
    SLLnode* head;
    SLList() : head(nullptr) {}
    void addToHead(int el) { head = new SLLnode(el, head); }
    ~SLList() {
        while (head) {
            SLLnode* tmp = head;
            head = head->next;
            delete tmp;
        }
    }
};

void Divisible(SLLnode* head, int K) {
    int minD = INT_MAX;
    int maxD = INT_MIN;
    bool found = false;
    
    for (SLLnode* curr = head; curr != nullptr; curr = curr->next) {
        if (curr->info % K == 0) {
            found = true;
            if (curr->info < minD) minD = curr->info;
            if (curr->info > maxD) maxD = curr->info;
        }
    }
    
    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() {
    SLList LIST;
    LIST.addToHead(50);
    LIST.addToHead(21);
    LIST.addToHead(32);
    LIST.addToHead(45);
    LIST.addToHead(11);
    LIST.addToHead(23);
    LIST.addToHead(90);
    LIST.addToHead(56);
    
    int K = 5;
    Divisible(LIST.head, K);
    return 0;
}

ความซับซ้อน

• เวลา: O(n) – เดินผ่าน linked list ครั้งเดียว
• พื้นที่: O(1) – ใช้ตัวแปรคงที่