หา Peak Element ใน Linked List ด้วย C++

ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมที่หา peak element ใน linked list ที่กำหนด

Peak element คือองค์ประกอบที่มากกว่าองค์ประกอบรอบข้าง มาดูขั้นตอนในการแก้ปัญหา

• สร้าง struct node สำหรับ linked list
• สร้าง linked list ด้วยข้อมูลจำลอง
• ตรวจสอบกรณีพื้นฐานเช่นว่าลinked list ว่างหรือมีความยาว 1
• เก็บองค์ประกอบแรกในตัวแปรที่เรียกว่า previous
• วนลูปผ่าน linked list
  • ตรวจสอบว่าองค์ประกอบปัจจุบันมากกว่าองค์ประกอบก่อนหน้าและถัดไปหรือไม่
  • คืนค่าถ้าเงื่อนไขเป็นจริง
  • อัปเดต previous element
• พิมพ์ผลลัพธ์

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

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

void insertNewNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    *head_ref = new_node;
}

int findPeakElement(struct Node* head) {
    if (head == NULL) {
        return -1;
    }
    if (head->next == NULL) {
        return head->data;
    }
    int prev = head->data;
    Node *current_node;
    for (current_node = head->next; current_node->next != NULL; current_node = current_node->next) {
        if (current_node->data > current_node->next->data && current_node->data > prev) {
            return current_node->data;
        }
        prev = current_node->data;
    }
    if (current_node->data > prev) {
        return current_node->data;
    }
    return -1;
}

int main() {
    struct Node* head = NULL;
    insertNewNode(&head, 7);
    insertNewNode(&head, 4);
    insertNewNode(&head, 5);
    insertNewNode(&head, 2);
    insertNewNode(&head, 3);
    cout << findPeakElement(head) << endl;
    return 0;
}

ผลลัพธ์

ถ้าคุณรันโค้ดด้านบน คุณจะได้ผลลัพธ์ดังนี้

5

สรุป

หากคุณมีคำถามในบทช่วยสอนนี้ ให้ระบุในส่วนความคิดเห็น