C 언어로 연결 리스트를 역순으로 뒤집는 프로그램 (재귀·반복 방식)

문제 개요

이 문제에서는 하나의 연결 리스트가 주어지며, 이를 역순으로 뒤집는 프로그램을 작성하는 것이 목표입니다. 프로그램은 주어진 연결 리스트의 링크 방향을 반대로 바꾸어, 뒤집힌 연결 리스트를 결과로 반환합니다.

연결 리스트(Linked List)란?

연결 리스트는 데이터 항목들을 담고 있는 노드들이 순서대로 연결된 자료구조입니다. 각 노드는 실제 데이터와 함께 다음 노드를 가리키는 링크(포인터)를 포함하고 있어, 노드들이 사슬처럼 이어진 형태를 이룹니다.

예시

9 -> 32 -> 65 -> 10 -> 85 -> NULL

역순 연결 리스트란?

역순 연결 리스트는 기존 리스트의 링크 방향을 모두 반대로 뒤집어 만든 연결 리스트입니다. 이때 원래 리스트의 마지막 노드가 새로운 헤드(head) 노드가 되고, 기존의 헤드 노드는 마지막 노드가 됩니다.

예시

위 연결 리스트를 뒤집으면 다음과 같은 형태가 됩니다.

85 -> 10 -> 65 -> 32 -> 9 -> NULL

뒤집기 알고리즘의 기본 원리

주어진 연결 리스트를 뒤집기 위해서는 세 개의 추가 포인터인 previous(이전), after(다음), current(현재)를 사용합니다.
먼저 previous와 after를 NULL로 초기화하고, current는 연결 리스트의 헤드로 설정합니다. 이후 원래 리스트의 끝(NULL)에 도달할 때까지 다음 과정을 반복 수행합니다.

after = current->next
current->next = previous
previous = current
current = after

각 단계에서 현재 노드의 next 포인터를 이전 노드를 가리키도록 변경하고, 세 포인터를 한 칸씩 앞으로 이동시키는 방식입니다. 이 과정을 끝까지 진행하면 리스트 전체의 링크 방향이 자연스럽게 반전됩니다.

방법 1. 꼬리 재귀(Tail Recursion) 방식

연결 리스트를 뒤집는 프로그램은 크게 두 가지 방법으로 작성할 수 있습니다. 하나는 반복(iterative) 방식이고, 다른 하나는 재귀(recursive) 방식입니다. 먼저 꼬리 재귀 방식으로 구현한 예제를 살펴보겠습니다. 꼬리 재귀는 재귀 호출이 함수의 마지막 연산이 되도록 작성하는 기법으로, 컴파일러 최적화에 따라 스택 사용 부담을 줄일 수 있다는 장점이 있습니다.

예제 코드

#include <stdio.h>
struct Node {
    int data;
    struct Node* next;
};
Node* insertNode(int key) {
    Node* temp = new Node;
    temp->data = key;
    temp->next = NULL;
    return temp;
}
void tailRecRevese(Node* current, Node* previous, Node** head){
    if (!current->next) {
        *head = current;
        current->next = previous;
        return;
    }
    Node* next = current->next;
    current->next = previous;
    tailRecRevese(next, current, head);
}
void tailRecReveseLL(Node** head){
    if (!head)
        return;
    tailRecRevese(*head, NULL, head);
}
void printLinkedList(Node* head){
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}
int main(){
    Node* head1 = insertNode(9);
    head1->next = insertNode(32);
    head1->next->next = insertNode(65);
    head1->next->next->next = insertNode(10);
    head1->next->next->next->next = insertNode(85);
    printf("Linked list : \t");
    printLinkedList(head1);
    tailRecReveseLL(&head1);
    printf("Reversed linked list : \t");
    printLinkedList(head1);
    return 0;
}

실행 결과

Linked list : 9 32 65 10 85
Reversed linked list : 85 10 65 32 9

방법 2. 반복(Iterative) 방식

다음은 while 반복문을 사용해 연결 리스트를 뒤집는 예제입니다. 각 노드의 next 포인터를 이전 노드를 가리키도록 변경해 가며 리스트를 딱 한 번만 순회하므로, 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

예제 코드

#include <stdio.h>
struct Node {
    int data;
    struct Node* next;
    Node(int data){
        this->data = data;
        next = NULL;
    }
};
struct LinkedList {
    Node* head;
    LinkedList(){
        head = NULL;
    }
    void interReverseLL(){
        Node* current = head;
        Node *prev = NULL, *after = NULL;
        while (current != NULL) {
            after = current->next;
            current->next = prev;
            prev = current;
            current = after;
        }
        head = prev;
    }
    void print() {
        struct Node* temp = head;
        while (temp != NULL) {
            printf("%d ", temp-> data);
            temp = temp->next;
        }
        printf("\n");
    }
    void push(int data){
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};
int main() {
    LinkedList linkedlist;
    linkedlist.push(85);
    linkedlist.push(10);
    linkedlist.push(65);
    linkedlist.push(32);
    linkedlist.push(9);
    printf("Linked List : \t");
    linkedlist.print();
    linkedlist.interReverseLL();
    printf("Reverse Linked List : \t");
    linkedlist.print();
    return 0;
}

실행 결과

Linked List : 9 32 65 10 85
Reverse Linked List : 85 10 65 32 9

마무리

두 방식 모두 연결 리스트를 성공적으로 뒤집을 수 있습니다. 일반적으로는 함수 호출 오버헤드가 없는 반복 방식이 실무에서 더 널리 사용되며, 재귀 방식은 로직이 직관적이라 알고리즘 학습 목적으로 유용합니다. 리스트의 길이와 상황에 맞는 방식을 선택해 적용해 보시기 바랍니다.