C 언어로 연결 리스트의 마지막 k개 노드 역순 출력하기 — 재귀 접근법

이 글에서는 재귀(Recursion) 기법을 활용해 연결 리스트(Linked List)의 뒤에서부터 k개의 노드를 출력하는 방법을 알아봅니다.

재귀 접근 방식이란 함수가 자기 자신을 반복적으로 호출하면서 조건이 충족될 때까지 실행되고 그 결과를 저장하는 프로그래밍 기법입니다. 연결 리스트에 재귀를 적용하면 리스트를 끝까지 먼저 탐색한 뒤, 되돌아오는 과정에서 원하는 노드들을 순서대로 처리할 수 있다는 장점이 있습니다.

예를 들어 리스트에 29, 34, 43, 56, 88이라는 노드가 저장되어 있고 k의 값이 2라고 가정해 보겠습니다. 이 경우 출력 결과는 마지막 k개 노드인 88과 56이 됩니다. 즉, 리스트를 역방향으로 거슬러 올라가며 마지막 노드부터 차례대로 값을 출력하게 됩니다.

예시

Linked List: 29->34->43->56->88
입력: 2
출력: 88 56

재귀 방식에서는 포인터 변수를 활용해 함수가 k번째 값에 도달할 때까지 자기 자신을 계속 호출하면서 리스트를 끝에서부터 순회하고, 동시에 순회 횟수를 추적합니다. 아래 코드는 이 알고리즘을 C 언어로 구현한 것입니다.

알고리즘

START
    Step 1 -> 구조체 타입으로 노드 변수 생성
        int data 선언
        node 타입 포인터 *next 선언
    Step 2 -> node* get(int data) 함수 선언
        malloc 함수로 newnode 생성
        newnode->data = data 설정
        newnode->next = NULL 설정
        newnode 반환
    Step 3 -> void lastval(node* head, int* count, int k) 함수 선언
        IF !head
            Return
        lastval(head->next, count, k) 재귀 호출
        count 증가
        IF (count <= k)
            head->data 출력
    Step 4 -> Main() 함수에서
        node* head = get(11)로 head 생성
        k와 count를 0으로 초기화
        lastval(head, &count, k) 호출
STOP

C 언어 구현 코드

#include<stdio.h>
#include<stdlib.h>

// 노드 구조체 정의
struct node {
    int data;
    struct node* next;
};

// 새 노드를 생성하는 함수
struct node* get(int data) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = data;
    newnode->next = NULL;
    return newnode;
}

// 리스트의 마지막 k개 값을 출력하는 함수
void lastval(struct node* head, int* count, int k) {
    if (!head)
        return;
    lastval(head->next, count, k);   // 리스트 끝까지 재귀 호출
    (*count)++;                      // 되돌아오며 카운트 증가
    if (*count <= k)
        printf("%d ", head->data);
}

int main() {
    // 리스트에 요소 삽입
    struct node* head = get(11);
    head->next = get(243);
    head->next->next = get(321);
    head->next->next->next = get(421);
    head->next->next->next->next = get(522);

    int k = 2, count = 0;
    printf("last %d nodes of a list are :", k);

    // 마지막 k개 노드 출력
    lastval(head, &count, k);
    return 0;
}

동작 원리

재귀 함수 lastval()은 먼저 head->next를 인자로 자기 자신을 호출하여 리스트의 맨 끝(NULL)까지 진입합니다. 더 이상 진행할 노드가 없으면 각 호출 지점으로 되돌아오면서 count를 하나씩 증가시키고, count가 k 이하일 때만 해당 노드의 데이터를 출력합니다. 이 과정 덕분에 별도의 역방향 탐색 없이도 마지막 노드부터 역순으로 값을 출력할 수 있습니다.

참고로 위 코드는 순수한 C 문법에 맞춰 참조(int&) 대신 포인터(int*)를 사용해 카운트를 전달하도록 작성되었습니다. 이렇게 해야 C 컴파일러에서 오류 없이 빌드할 수 있습니다.

실행 결과

위 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.

last 2 nodes of a list are :522 421