Namaran

Code daily. Without assist.

2026-10-02

clear_list.cpp

#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

void clear(std::unique_ptr<Node>& head) {
}

head から next でつながる単方向リストのノードをすべて解放し、head を空にする clear を書いてください。ノードが100万個あっても、使うスタックの深さはノードの数によらず一定にします。head がもともと空なら何もしません。

入力例 1

std::unique_ptr<Node> h; for (int i = 0; i < 3; ++i) h = std::make_unique<Node>(i, std::move(h)); clear(h); std::cout << (h == nullptr);

出力例 1

1

入力例 2

std::unique_ptr<Node> h; for (int i = 0; i < 1'000'000; ++i) h = std::make_unique<Node>(i, std::move(h)); clear(h); std::cout << (h == nullptr);

出力例 2

1

入力例 3

std::unique_ptr<Node> h; clear(h); std::cout << (h == nullptr);

出力例 3

1
Reference
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

void clear(std::unique_ptr<Node>& head) {
    while (head)
        head = std::move(head->next);
}

head.reset() の1行でもノードはすべて解放されますが、先頭のノードを破棄すると、メンバの next のデストラクタが次のノードを破棄し、それがさらに次のノードを破棄します。デストラクタの中から次のデストラクタを呼ぶ連鎖なので、ノード1つにつきスタックフレームが1つ積まれ、例2の100万個ではスタックが足りずに落ちます。コンパイラがこの連鎖をループに直してくれる保証はありません。

参考実装は、先頭のノードを1つずつ外していきます。head = std::move(head->next) のムーブ代入は、まず右辺の head->next から所有権を取り出して空にし、それから head が持っていた古い先頭ノードを破棄します1。破棄される時点でそのノードの next はもう空なので、デストラクタは次のノードへ連鎖しません。ループの1周で1ノードずつ解放され、スタックの深さは一定のままです。

掲載したのは参考実装で、唯一の正解ではありません。auto next = std::move(head->next); で次のノードを退避してから head = std::move(next); と代入する、手順を2行に分けた書き方もあります。

  1. 規格は unique_ptr のムーブ代入の効果を reset(u.release()) と定めています。reset も、新しいポインタを先に格納してから古いポインタを削除します。