C++でリンクリスト内の最初の非重複要素を見つけるプログラム

この問題では、サイズNのリンクリストLLが与えられます。求められているのは、リンクリスト内で最初に一度だけ出現する要素（非重複要素）を見つけるプログラムを作成することです。

リンクリストとは、データ構造同士をポインタ（リンク）で順番につなげた一連のデータ構造です。

問題の例

具体例を使って問題を確認してみましょう。

入力：LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5
出力：1

解説：

このリンクリストでは、一度だけ出現する要素は「1」と「5」です。
そのうち、リンクリストの先頭に近い方に出現しているのは「1」なので、答えは1となります。

解決アプローチ

この問題を解くための効果的な方法は、ハッシュテーブル（ハッシュマップ）を使って各要素の出現回数を記録することです。

手順は以下の通りです。

1. リンクリストを先頭から順に走査し、各要素の出現頻度をハッシュマップに記録します。初めて登場する要素は出現回数1として登録し、すでに存在する要素は出現回数をインクリメントします。
2. 走査が完了したら、再度リンクリストを先頭から走査し、ハッシュマップ上で出現回数が1になっている要素を探します。
3. 最初に見つかった要素を返します。該当する要素が存在しない場合は-1を返します。

この方法では、時間計算量はO(N)、空間計算量もO(N)となり、効率的に解くことができます。

実装例

以下は、上記の解法の動作を示すC++プログラムです。

#include<bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   struct Node* next;
};
void push(struct Node** head_ref, int new_data){
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
int findFirstNonRepLL(struct Node *head){
   unordered_map<int, int> freqMap;
   for (Node *temp=head; temp!=NULL; temp=temp->next){
      freqMap[temp->data]++;
   }
   for (Node *temp=head; temp!=NULL; temp=temp->next){
      if (freqMap[temp->data] == 1){
         return temp->data;
      }
   }
   return -1;
}
int main(){
   struct Node* head = NULL;
   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<<"リンクリストの最初の非重複要素は "<<findFirstNonRepLL(head);
   return 0;
}

実行結果

リンクリストの最初の非重複要素は 1

このように、ハッシュマップを活用することで、2回のリンクリスト走査だけで最初の非重複要素を簡単かつ効率的に特定できます。