main や const はそのままで、print_int_list だけを変更するなら、
O(n
2)の時間がかかるやり方は、
コード:
void print_int_list(list l) {
for (list head = l->next, p = head; ; p = l) {
l = p;
while ((l = l->next)->next != p) ;
printf("[%d]", l->element);
if (l == head) break;
}
printf("\n");
}
時間は O(n) だけど、O(n) のメモリを余計に必要とするやり方は、
コード:
void print(list p, list l) {
if (p != l) print(p->next, l);
printf("[%d]", p->element);
}
void print_int_list(list l) {
print(l->next, l);
printf("\n");
}
循環リストを逆順に繋ぎ変えることで、余計なメモリを使わず、
時間も O(n) で済むやり方
コード:
void print_int_list(list l) {
list head = l->next, p = head, q = l, next;
while (1) {
next = p->next, p->next = q, q = p;
if (p == l) break;
p = next;
}
while (1) {
printf("[%d]", q->element);
if (q == head) break;
q = q->next;
}
printf("\n");
while (1) {
next = p->next, p->next = q, q = p;
if (p == head) break;
p = next;
}
}
以上すべて無限に出力するのはやめています。
また、循環リストには最低 1個のデータがあるものとします。
質問に回答したので、理解できたかどうかの返信を必ずお願いします。