HackerRankのLinked Lists問題の解法と解析

まず、問題の要件を理解しましょう。問題では、与えられたリンクリストから重複する要素を削除する必要があります。具体的には、与えられたリンクリストの要素を順番に見ていき、重複する要素があればそれを削除し、最終的なリンクリストを返す必要があります。

問題の解法にはいくつかの方法がありますが、ここでは2つのアプローチを紹介します。

アプローチ1: ハッシュマップを使用する方法このアプローチでは、ハッシュマップを使用してリンクリストの要素を追跡します。具体的なステップは以下の通りです。

空のハッシュマップを作成します。
リンクリストの要素を順番に見ていきます。
ハッシュマップに要素を追加します。既にハッシュマップに存在する要素は無視します。
リンクリストの最後の要素まで繰り返します。
新しいリンクリストを作成し、ハッシュマップのキーを順番に追加します。
新しいリンクリストを返します。

以下は、このアプローチのJavaScriptのコード例です。

function removeDuplicates(head) {
  if (head == null) {
    return head;
  }
  const map = new Map();
  let current = head;
  let previous = null;
  while (current !== null) {
    if (map.has(current.data)) {
      previous.next = current.next;
    } else {
      map.set(current.data, true);
      previous = current;
    }
    current = current.next;
  }
  return head;
}

アプローチ2: 2つのポインタを使用する方法このアプローチでは、2つのポインタを使用してリンクリストをスキャンします。具体的なステップは以下の通りです。

リンクリストを順番にスキャンします。
現在の要素を基準にし、次の要素と比較します。
重複する要素があれば、現在の要素のnextポインタを次の次の要素に更新します。
リンクリストの最後の要素まで繰り返します。
更新されたリンクリストを返します。

以下は、このアプローチのJavaScriptのコード例です。

function removeDuplicates(head) {
  if (head == null) {
    return head;
  }
  let current = head;
  while (current.next !== null) {
    if (current.data === current.next.data) {
      current.next = current.next.next;
    } else {
      current = current.next;
    }
  }
  return head;
}

以上が、HackerRankの「More Linked Lists」問題の解法と解析です。どちらのアプローチも重複する要素を効率的に削除することができます。この記事が役立つことを願っています。