หาค่า Min และ Max ใน Singly Circular Linked List ใน C++

ในบทความนี้เราจะมาดูวิธีการหาค่าต่ำสุดและสูงสุดจาก Singly Circular Linked List แนวคิดพื้นฐานคือ Next ของโหนดสุดท้ายจะชี้ไปที่โหนดแรก โหนดแรกก็ถูกชี้โดย Start Pointer เมื่อ Insert Element ใหม่ Next ของโหนดใหม่จะถูกอัปเดตเป็น Address ของ Start Node

เริ่มต้น Min กำหนดเป็น Positive Infinity และ Max เป็น Negative Infinity Traverse List จากซ้ายไปขวา ถ้า Element ปัจจุบันน้อยกว่า Min ให้อัปเดต Min ถ้ามากกว่า Max ให้อัปเดต Max ดังนั้นจะได้ค่า Min และ Max

ตัวอย่างโค้ด C++

#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);
}

ผลลัพธ์

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