Tìm kiếm phần tử trong danh sách liên kết đơn bằng C++

Cho một danh sách liên kết đơn, nhiệm vụ là tìm kiếm một phần tử cho trước. Nếu tìm thấy in "Present", ngược lại "Not Present". Ví dụ:

Đầu vào 1: Danh sách: 1→2→3→4→5→6, tìm 7 → Not Present.

Đầu vào 2: Danh sách: 1→2→3→4→5, tìm 2 → Present.

Phương pháp giải quyết

Có hai cách: đệ quy và lặp.

• Đệ quy: Nếu node hiện tại là NULL → false. Nếu dữ liệu khớp → true. Ngược lại gọi đệ quy cho node tiếp theo.
• Lặp: Duyệt từ head đến cuối, so sánh từng node.

Ví dụ mã nguồn (đệ quy)

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

void insertAtHead(Node* &head, int data) {
    Node* n = new Node(data);
    n->next = head;
    head = n;
}

bool searchRecursive(Node* head, int key) {
    if (!head) return false;
    if (head->data == key) return true;
    return searchRecursive(head->next, key);
}

void printList(Node* head) {
    while (head) {
        cout << head->data << "->";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Node* head = nullptr;
    insertAtHead(head, 5);
    insertAtHead(head, 4);
    insertAtHead(head, 3);
    insertAtHead(head, 2);
    insertAtHead(head, 1);
    printList(head);
    cout << (searchRecursive(head, 7) ? "Present" : "Not Present") << endl;
    return 0;
}

Kết quả

Not Present

Đệ quy đơn giản nhưng có thể gây tràn stack nếu danh sách quá dài. Phương pháp lặp an toàn hơn.