練習問題

Linked Listに関するちょっと難しい問題に出会ったのでメモ。

struct node { Item item; node *next; };
typedef node *link;
typedef link Node;

1. いくつかのNodeが存在して、その全てがnextにnull pointerを持っていない（つまり、全てのNodeが自分自身かその他のNodeを指している）場合、あるNodeからリンクをたどっていけば、必ず循環におちいることを証明せよ。

2. 1の条件のもと、あるNodeからリンクをたどっていった場合、いくつの異なるNodeをたどることができるかを計算するプログラムを書け。ただし、Nodeを変更してはならず、定数量以上の追加のメモリスペースを使ってはならない。

3. 2の条件のもと、２つのNodeからそれぞれリンクをたどっていった場合、２つが同じ循環におちいるかどうかを判断するプログラムを書け。