Go言語で90%のリンクリスト問題を解決する3つのテクニック

この記事では、LeetCode-Go を使用して、リンクリストの逆転、環検出、およびマージを行う方法について説明します。これらのテクニックは、インタビューとアルゴリズムの練習で役立つでしょう。

### LeetCode-Goの特徴

LeetCode-Goは、Go言語で書かれたLeetCodeの問題解法集です。全ての問題が100%のテストカバレッジを持ち、実行時間も最適化されています。各問題は独立したディレクトリに配置されており、例えば`leetcode/0206.Reverse-Linked-List/`のように参照できます。

### テクニック1: リンクリストの逆転 - 二重ポインタ法

リンクリストの逆転は、よく見られる問題の一つです。LeetCode-Goの206. Reverse Linked Listでは、効率的な二重ポインタ法を使用しています。

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        next := head.Next
        head.Next = prev
        prev = head
        head = next
    }
    return prev
}

**主な考え方**: 1. 二つのポインタ `prev` と `head` を使用し、それぞれ逆転済み部分の先頭と逆転待ち部分の先頭を表します。 2. リンクリストを走査し、`head` の `Next` を `prev` に設定し、ポインタを更新します。 3. 時間計算量は O(n)、空間計算量は O(1) であり、最適な解法です。 ### テクニック2: 環検出 - 速い指針と遅い指針法

リンクリストに環があるかどうかを検出し、環の入口を見つける問題は別の典型的な問題です。LeetCode-Goの142. Linked List Cycle IIでは、速い指針と遅い指針法を使用しています。

func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }
    hasCycle, slow := hasCycle142(head)
    if !hasCycle {
        return nil
    }
    fast := head
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }
    return fast
}

func hasCycle142(head *ListNode) (bool, *ListNode) {
    fast := head
    slow := head
    for slow != nil && fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true, slow
        }
    }
    return false, nil
}

**主な考え方**: 1. 速い指針と遅い指針を使用して、リンクリストに環があるかどうかを判断します。速い指針は2ステップずつ、遅い指針は1ステップずつ進みます。両者が一致すれば環があります。 2. 環が存在する場合、速い指針をリストの先頭に戻し、遅い指針と一緒に1ステップずつ進める。再び一致したノードが環の入口です。 3. 時間計算量は O(n)、空間計算量は O(1) であり、追加のメモリは必要ありません。 ### テクニック3: 2つの順序付けられたリンクリストのマージ - 再帰法

2つの順序付けられたリンクリストをマージすることは基本的な操作です。LeetCode-Goの21. Merge Two Sorted Listsでは、再帰法を使用して簡潔かつ効率的に実装しています。

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val < l2.Val {
        l1.Next = mergeTwoLists(l1.Next, l2)
        return l1
    }
    l2.Next = mergeTwoLists(l1, l2.Next)
    return l2
}

**主な考え方**: 1. 2つのリストの先頭ノードを比較し、値が小さい方をマージ後のリストの先頭に設定します。 2. 残りのノードを再帰的にマージします。 3. 時間計算量は O(n+m)、空間計算量は O(n+m)（再帰呼び出しスタック）であり、コードは簡潔で理解しやすいです。 ### LeetCode-Goを使ってスキルを向上させる方法 1. **プロジェクトをクローン**: `git clone https://gitcode.com/GitHub_Trending/le/LeetCode-Go` 2. **問題を選択**: `leetcode/` ディレクトリ内にある対応する問題フォルダを選択します。例: `0206.Reverse-Linked-List/` 3. **ソースコードを学ぶ**: `*.go` ファイル内のコードを読み、解法と最適化テクニックを理解します。 4. **自分で実装**: 自分で実装を試み、ソースコードと比較して違いを見つけます。 これらの3つの主要なテクニックを掌握することで、多くのリンクリストの問題を解決できるようになります。LeetCode-Goには、さらに高度なリンクリストの問題と解法も含まれていますので、ぜひ探求してみてください。