#include <stdio.h>
#include <stdlib.h>
struct node {  //연결릿트 노드
    int x;
    struct node* next;
};
struct node* node_alloc(int x, struct node* next){  //노드 생성 함수
    struct node*temp=(struct node*)malloc(sizeof(struct node));
    temp->x=x;  //데이터 저장
    temp->next = next;  //다음 노드 연결
    return temp;
}
void recRev(struct node** head_ref);
void print(struct node* n){  //연결리스트 출력
    while(n){
        printf("%d  ", n->x);
        n=n->next;
    }
    printf("\n");
}
int main(){  //역순으로 삽입
    struct node *n=node_alloc(1, NULL);
    n=node_alloc(2, n);
    n=node_alloc(3, n);
    n=node_alloc(4, n);   //4->3->2->1
    print(n); //ㄱ
    recRev(&n);  //재귀 역순
    return 0;
}
void recRev(struct node** head_ref){
    struct node* first;
    struct node* rest;
    if(*head_ref==NULL) return;  //빈 리스트면 종료
    
    first=*head_ref;  //첫 노드
    rest=first->next;  //나머지 리스트
    
    if(rest==NULL) return;   //노드가 1개면 종료
    
    recRev(&rest);  //나머지 리스트를 재귀적으로 뒤집기
    
    first->next->next=first; //방향 뒤집기
    
    first->next=NULL;  //first를 마지막으로 만들기
    
    print(rest);//ㄴ    //현재 상태 출력하기
    
    *head_ref=rest;  //새로운 head 저장하기
}