Tìm phần tử không lặp đầu tiên trong danh sách liên kết C++

Mô tả bài toán

Cho danh sách liên kết. Tìm giá trị đầu tiên chỉ xuất hiện một lần.

Ví dụ

LL: 4→6→2→4→1→2→6→5 → Output: 1 (1 và 5 xuất hiện 1 lần, 1 xuất hiện trước).

Giải thuật

1. Duyệt list, dùng unordered_map đếm tần suất.
2. Duyệt lại list, trả về node đầu tiên có freq == 1.

Mã nguồn C++

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

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

void push(Node** head, int val) {
    Node* n = new Node{val, *head};
    *head = n;
}

int findFirstNonRepLL(Node* head) {
    unordered_map<int,int> freq;
    for (Node* p=head; p; p=p->next) freq[p->data]++;
    for (Node* p=head; p; p=p->next)
        if (freq[p->data] == 1) return p->data;
    return -1;
}

int main() {
    Node* head = nullptr;
    push(&head,5); push(&head,6); push(&head,2); push(&head,1);
    push(&head,4); push(&head,2); push(&head,6); push(&head,4);
    cout << "First non-repeating: " << findFirstNonRepLL(head);
    return 0;
}

Đầu ra

The first non repeating element of the linked list is 1