Tìm phần tử đỉnh trong danh sách liên kết C++

Tìm peak trong danh sách liên kết đơn: node có dữ liệu lớn hơn cả node trước và sau.

Phương pháp

• Xử lý trường hợp rỗng, 1 node.
• Lưu giá trị node trước (prev).
• Duyệt từ node thứ 2 đến node trước cuối: so sánh current với prev và next.
• Cuối cùng kiểm tra node cuối.

Ví dụ mã nguồn

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

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

void insert(Node** head, int data) {
    Node* n = new Node{data, *head};
    *head = n;
}

int findPeak(Node* head) {
    if (!head) return -1;
    if (!head->next) return head->data;
    int prev = head->data;
    for (Node* cur = head->next; cur->next; cur = cur->next) {
        if (cur->data > prev && cur->data > cur->next->data)
            return cur->data;
        prev = cur->data;
    }
    // kiểm tra node cuối
    Node* last = head;
    while (last->next) last = last->next;
    if (last->data > prev) return last->data;
    return -1;
}

int main() {
    Node* head = nullptr;
    insert(&head, 7);
    insert(&head, 4);
    insert(&head, 5);
    insert(&head, 2);
    insert(&head, 3);
    // danh sách: 3->2->5->4->7
    cout << findPeak(head); // 5
    return 0;
}

Kết quả

5

Danh sách: 3→2→5→4→7. Peak là 5 (lớn hơn 2 và 4).