연결 리스트의 마지막 k개 노드를 역순으로 출력하기
이번 글에서는 연결 리스트(Linked List)의 마지막 k개 노드를 역순으로 출력하는 방법을 다룹니다. 문제 해결에는 재귀가 아닌 반복문(iterative) 기반 접근법을 사용합니다.
반복문 방식은 조건이 참(true)인 동안 계속 실행되는 루프를 활용하는 기법입니다. 재귀 호출에 따른 함수 호출 스택 오버헤드가 없기 때문에, 큰 크기의 리스트를 다룰 때에도 안정적으로 동작한다는 장점이 있습니다.
예를 들어, 연결 리스트에 29, 34, 43, 56, 88이라는 노드가 저장되어 있고 k값이 2라면, 마지막 2개 노드인 56과 88이 순서대로 출력됩니다.
예시
연결 리스트: 29->34->43->56->88
입력: 2
출력: 56 88
접근 방식
리스트의 마지막 k개 원소만 추출하면 되므로, 가장 효율적인 방법은 스택(Stack) 자료구조를 활용하는 것입니다. 리스트를 순회하며 값을 배열에 역방향으로 채워 넣으면, 배열의 앞부분부터 자연스럽게 리스트의 뒤쪽 원소들이 위치하게 됩니다. 이후 이 값들을 k번째까지 차례로 꺼내어 출력하면 연결 리스트의 마지막 노드들을 역순으로 얻을 수 있습니다.
아래 코드는 위 알고리즘의 C언어 구현 예시입니다.
알고리즘
START
Step 1 -> 구조체 타입의 노드 변수 생성
정수형 data 선언
node 타입 포인터 *next 선언
Step 2 -> struct node* intoList(int data) 생성
malloc으로 newnode 생성
newnode->data = data 설정
newnode->next = NULL 설정
newnode 반환
Step 3 -> void rev(struct node* head, int count, int k) 함수 선언
struct node* temp1 = head 생성
While(temp1 != NULL) 반복
count++
temp1 = temp1->next
반복 종료
int array[count], temp2 = count, i 선언
temp1 = head 설정
While(temp1 != NULL) 반복
array[--temp2] = temp1->data 설정
temp1 = temp1->next
반복 종료
For(i = 0; i < k; i++) 반복
array[i] 출력
반복 종료
Step 4 -> main() 함수 내에서
struct node* head = intoList(9) 로 리스트 생성
k=3, count=0 설정
rev(head, count, k) 호출
STOP
C언어 구현 코드
#include<stdio.h>
#include<stdlib.h>
// 노드의 구조체 정의
struct node {
int data;
struct node *next;
};
// 새로운 노드를 삽입하는 함수
struct node* intoList(int data) {
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = data;
newnode->next = NULL;
return newnode;
}
// 노드의 원소를 역순으로 출력하는 함수
void rev(struct node* head, int count, int k) {
struct node* temp1 = head;
// 첫 번째 순회: 전체 노드 개수 계산
while(temp1 != NULL) {
count++;
temp1 = temp1->next;
}
int array[count], temp2 = count, i;
temp1 = head;
// 두 번째 순회: 배열의 뒤에서부터 값 저장 (역방향)
while(temp1 != NULL) {
array[--temp2] = temp1->data;
temp1 = temp1->next;
}
// 마지막 k개 원소 출력
for(i = 0; i < k; i++)
printf("%d ", array[i]);
}
int main() {
printf("\nreverse of a list is : ");
struct node* head = intoList(9); // 리스트에 원소 삽입
head->next = intoList(76);
head->next->next = intoList(13);
head->next->next->next = intoList(24);
head->next->next->next->next = intoList(55);
head->next->next->next->next->next = intoList(109);
int k = 3, count = 0;
rev(head, count, k); // 역순 출력 함수 호출
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
reverse of a list is : 109 55 24
동작 원리 및 복잡도 분석
위 코드의 동작 흐름은 다음과 같습니다.
1단계: 먼저 리스트를 한 번 순회하면서 전체 노드의 개수(count)를 계산합니다. 위 예제에서는 총 6개의 노드가 있으므로 count는 6이 됩니다.
2단계: 다시 리스트를 처음부터 순회하면서 각 노드의 데이터를 배열의 뒤쪽 인덱스부터 저장합니다. 이렇게 하면 배열의 앞부분에 리스트의 마지막 원소들이 오게 되어, 사실상 리스트 전체가 역순으로 변환된 것과 같은 효과를 얻습니다.
3단계: 배열의 인덱스 0부터 k-1번째까지의 값을 출력하면, 곧 연결 리스트의 마지막 k개 노드가 역순으로 출력됩니다.
- 시간 복잡도: O(n) — 리스트를 두 번 순회하므로 노드 수 n에 비례합니다.
- 공간 복잡도: O(n) — 모든 노드 값을 저장할 배열이 필요합니다.
만약 k가 작고 n이 매우 큰 상황이라면, '두 포인터(two-pointer)' 기법을 사용해 리스트를 한 번만 순회하면서 마지막 k개 노드를 찾는 최적화 방법도 고려해볼 수 있습니다.