(循環)リストを逆順で表示したい

[mrte]

単方向循環リストを実装し、その内容を表示するものを作成して、その表示順番を逆順にしたいのですが方法が分からないので教えて欲しいです。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int elementtype;
struct node{
    elementtype element;
    struct node *next;
};
typedef struct node* list;

list cons(elementtype e, list l){//リストlの先頭にeを追加したリストを返す
    list n = (struct node *)malloc(sizeof(struct node *));
    n->element = e;
    n->next = l;
    return n;
}

void print_int_list(list l){//リストlに含まれる要素を先頭から出力
    while(l != NULL){printf("[%d]",l->element);l = l->next;}
    printf("\n");
}

int main(){
    int i;
    char buf[128];
    list l = NULL;
    list head;
    while(fgets(buf,sizeof(buf),stdin) != NULL){
        sscanf(buf,"%d",&i);
        l = cons(i, l);
    }
    head = l;
    while(l->next != NULL){//リストを循環リストにする
        l = l->next;
    }
    l->next = head;     
    print_int_list(l);
    return 0;
}

【入力】
1
2
3
4
5
【出力(現在)】
[1][5][4][3][2][1][5][4][3][2][1]......
【出力(理想)】
[1][2][3][4][5][1][2][3][4][5].....

[かずま]

main や const はそのままで、print_int_list だけを変更するなら、

O(n²)の時間がかかるやり方は、

コード:

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個のデータがあるものとします。

質問に回答したので、理解できたかどうかの返信を必ずお願いします。

[mrte]

丁寧な回答ありがとうございます。
無事理解することができました、またただ動くだけでなく計算量やメモリの使用量を考えることの重要性を感じました。