이 문제의 과제는 연결 리스트(Linked List)의 노드를 끝에서부터 역순으로 출력하되, 추가 공간을 사용하지 않는 것입니다. 즉, 별도의 변수나 자료구조를 만들지 않고, 첫 번째 노드를 가리키고 있는 헤드 포인터만 활용해야 합니다.
예시
입력: 10 21 33 42 89 출력: 89 42 33 21 10
연결 리스트를 역순으로 출력하는 방법은 여러 가지가 있습니다. 예를 들어 재귀 호출 방식(스택 메모리라는 추가 공간 사용), 리스트 자체를 뒤집는 방식(원본 리스트가 변경됨), 스택에 요소를 모두 넣었다가 하나씩 꺼내며 출력하는 방식(O(n) 공간 필요) 등이 있습니다. 하지만 이 방법들은 모두 O(1)보다 많은 공간을 사용하거나 원본 데이터에 손실을 일으킵니다.
O(1) 공간으로 해결하는 방법
추가 공간을 거의 사용하지 않고 결과를 얻으려면 다음과 같은 접근 방식을 사용할 수 있습니다.
- 연결 리스트에 있는 노드의 총 개수를 먼저 계산합니다.
- i = n부터 i = 1까지 반복문을 돌리면서 각 위치(i번째)의 노드 데이터를 순서대로 출력합니다.
알고리즘
START
Step 1 -> 구조체 타입의 노드 변수 생성
int data 선언
node 타입 포인터 *next 선언
Step 2 -> 함수 int get(struct node* head) 선언
int count=0 변수 선언
struct node *newme=head 선언
newme!=NULL인 동안 반복
count를 1씩 증가
newme = newme->next 설정
반복 종료
count 반환
Step 3 -> 함수 void push(node** headref, char newdata) 선언
malloc으로 메모리 할당
newnode->data = newdata 설정
newnode->next = (*headref) 설정
(*headref) = newnode 설정
Step 4 -> 함수 int getN(struct node* head, int n) 선언
struct node* cur = head 선언
for(int i=0; i<n-1 && cur != NULL; i++) 반복
cur = cur->next 설정
반복 종료
cur->data 반환
Step 5 -> 함수 void reverse(node *head) 선언
int n = get(head) 선언
for(int i=n; i>=1; i--) 반복
getN(head,i) 출력
반복 종료
Step 6 -> main() 함수에서
node* head = NULL로 리스트 생성
push(&head, 89) 등으로 요소 삽입
reverse(head) 호출
STOP구현 코드
#include<stdio.h>
#include<stdlib.h>
//노드 구조체 정의
struct node {
int data;
struct node* next;
};
void push(struct node** headref, int newdata) {
struct node* newnode = (struct node*) malloc(sizeof(struct node));
newnode->data = newdata;
newnode->next = (*headref);
(*headref) = newnode;
}
int get(struct node* head) {
int count = 0;
struct node* newme = head;
while (newme != NULL){
count++;
newme = newme->next;
}
return count;
}
int getN(struct node* head, int n) {
struct node* cur = head;
for (int i=0; i<n-1 && cur != NULL; i++)
cur = cur->next;
return cur->data;
}
void reverse(node *head) {
int n = get(head);
for (int i=n; i>=1; i--)
printf("%d ", getN(head, i));
}
int main() {
struct node* head = NULL; //첫 번째 노드 생성
push(&head, 89); //리스트에 요소 삽입
push(&head, 42);
push(&head, 33);
push(&head, 21);
push(&head, 10);
reverse(head); //역순 출력 함수 호출
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.
89 42 33 21 10
이 방식은 리스트를 수정하지 않으면서도 상수 크기의 변수 몇 개만 사용해 역순 출력을 수행할 수 있다는 장점이 있습니다. 다만 getN 함수가 매번 처음부터 n번째 노드까지 이동해야 하므로 시간 복잡도는 O(n²)가 된다는 점을 참고하시기 바랍니다. 공간 효율성이 우선이라면 이 방법이 적합합니다.