참고자료
Program to Create a Circular Linked List of N Nodes and Display it in Reverse Order - javatpoint
Program to Create a Circular Linked List of N Nodes and Display it in Reverse Order on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.
www.javatpoint.com
circular linked list를 다이어그램으로 나타내면 아래와 같다.
이를 reverse하게 display하려면 tail부터 시작해서 head에 이르는 순서로 출력해야한다.
처음 이 문제를 접했을 때 recursive(재귀)를 이용하면 어떨까? 라는 생각을 했지만 실제 코드로 옮기진 못했다.
대안으로 다음과 같이 reverse()함수를 선언해서 list 자체를 반대 방향으로 바꾸려 했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
void reverse(){
struct node *temp = head;
struct node *temp_2 = NULL;
struct node *temp_3 = NULL;
if(head==NULL||head==tail){
return;
}
else{
temp_2 = temp->next;
temp_3 = temp_2->next;
do{
temp_2->next = temp;
temp = temp_2;
temp_2 = temp_3;
temp_3 = temp_3->next;
}while(temp!=head);
head=tail;
tail=temp;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
이렇게 리스트를 reverse로 바꾸어서 display하는 것도 하나의 방법이다.
만약 list를 변경하지 않고 reverse방향으로 출력하려면 어떻게 해야 할까?
recursive하게 function call을 쌓아서 출력하는 방법이 있다.
아래와 같이 재귀함수를 이용하면 함수 call이 stack 형식으로 쌓여 tail부터 head의 순서로 출력된다.
|
1
2
3
4
5
6
7
8
|
void reverse(struct node *current) {
if(current->next == head) {
printf("%d ",current->data);
return;
}
reverse(current->next);
printf("%d ",current->data);
}
|
current->next가 head가 될때까지 reverse함수는 계속 reverse(current->next)를 호출한다.
if문의 조건에 걸리게 되면 tail->data를 출력하고 return이 되어 함수콜이 종료되고 stack형식으로 쌓여있던 함수콜중 가장 최근에 호출된 reverse(current->next) 즉 reverse(tail의 한칸 전)이 호출되고 결과적으로 tail 에서 head까지의 순서로 data 값들이 출력된다.
*중요개념 : 재귀함수, stack, LastComeFirstOut, recursive call
댓글