C++で連結リスト内のすべての0を先頭に移動する方法

問題の概要

ランダムな整数と0を含む連結リストが与えられます。この問題では、リスト内のすべての0を連結リストの先頭に移動させる必要があります。具体的な例を見てみましょう。

入力

3 -> 0 -> 1 -> 0 -> 0 -> 1 -> 0 -> 0 -> 3 -> NULL

出力

0->0->0->0->0->3->1->1->3->NULL

出力を見ると、すべての0がリストの先頭に集められ、それ以外の要素は元の相対的な順序を保ったまま後ろに並んでいることがわかります。

アルゴリズム

1. 連結リストを初期化します。
2. 連結リストが空、またはノードが1つしかない場合は、そのまま処理を終了します。
3. 現在のノードと前のノードを追跡するため、それぞれ2番目のノードと先頭のノードで2つのポインタを初期化します。
4. 連結リストの末尾に到達するまで反復処理を行います。
5. 現在のノードの値が0である場合、そのノードを新しい先頭（ヘッド）にします。ノードを新しい先頭にすることで、自動的にリストの先頭へ移動されます。このとき、新しい先頭のnextポインタを、それまでの先頭ノードで更新します。その後、現在のノードと前のノードの変数の値を適切に更新します。

実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *next;
};
void addNewNode(struct Node **head, int data) {
    struct Node *newNode = new Node;
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}
void moveZeroes(struct Node **head) {
    if (*head == NULL) {
        return;
    }
    struct Node *temp = (*head)->next, *prev = *head;
    while (temp != NULL) {
        if (temp->data == 0) {
            Node *current = temp;
            temp = temp->next;
            prev->next = temp;
            current->next = *head;
            *head = current;
        } else {
            prev = temp;
            temp = temp->next;
        }
    }
}
void printLinkedList(struct Node *head) {
    while (head != NULL) {
        cout << head->data << "->";
        head = head->next;
    }
    cout << "NULL" << endl;
}
int main() {
    struct Node *head = NULL;
    addNewNode(&head, 3);
    addNewNode(&head, 0);
    addNewNode(&head, 1);
    addNewNode(&head, 0);
    addNewNode(&head, 0);
    addNewNode(&head, 1);
    addNewNode(&head, 0);
    addNewNode(&head, 0);
    addNewNode(&head, 3);
    moveZeroes(&head);
    printLinkedList(head);
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、以下の結果が得られます。

0->0->0->0->0->3->1->1->3->NULL

計算量

このアルゴリズムは連結リストを一度だけ走査するため、時間計算量はO(n)です。また、追加のメモリを使用しないため、空間計算量はO(1)となります。ポインタの付け替えだけでノードを移動できるのが、連結リストならではの利点と言えるでしょう。