기술면접 - 단일 연결 리스트 역순: 반복적 및 재귀적 방법

단일 연결 리스트를 역순으로 만드는 것은 컴퓨터 과학에서 중요한 문제로, 코딩 인터뷰와 데이터 구조 강의에서 자주 등장합니다. 단일 연결 리스트는 각 노드가 값과 다음 노드를 가리키는 포인터를 포함하는 선형 데이터 구조입니다. 마지막 노드는 NULL을 가리킵니다. 리스트를 역순으로 만들면 마지막 노드가 첫 번째 노드가 되고, 그 다음 노드가 두 번째가 되는 식으로 순서가 바뀝니다.

이 글에서는 단일 연결 리스트를 역순으로 만드는 두 가지 일반적인 방법인 반복적 방법과 재귀적 방법을 C 언어로 구현합니다. C 코드 예제와 함께 두 방법의 차이점을 자세히 설명합니다.

난이도: 3/10

근거: 반복/재귀 모두 O(n) 시간. 포인터 조작이 약간 까다로울 수 있지만, 기본적인 링크드 리스트 문제.

1. 단일 연결 리스트 이해하기

알고리즘을 살펴보기 전에 단일 연결 리스트의 구조를 간단히 알아보겠습니다. 값이 1, 2, 3, 4인 노드로 구성된 리스트를 예로 들어 보겠습니다:

• 원래 리스트: 1 -> 2 -> 3 -> 4 -> NULL
• 역순 리스트: 4 -> 3 -> 2 -> 1 -> NULL

각 노드는 다음과 같은 필드를 가집니다:

• data: 노드의 값(예: 1, 2, 3, 4)
• next: 다음 노드를 가리키는 포인터(마지막 노드에서는 NULL)

목표는 이 next 포인터의 방향을 바꿔 리스트를 역순으로 만드는 것입니다.

2. 반복적 방법

반복적 방법은 세 개의 포인터를 사용하여 리스트를 한 번 순회하며 링크를 역순으로 변경합니다. 이 방법은 메모리 사용이 적고 효율적입니다.

단계:

1. 세 개의 포인터를 초기화합니다:
   • previous: 처음에는 NULL(첫 번째 노드 앞에는 노드가 없으므로).
   • current: 리스트의 헤드에서 시작.
   • next: 다음 노드를 임시로 저장.
2. current가 NULL이 아닌 동안 다음을 반복:
   • next에 다음 노드를 저장(next = current->next).
   • current의 링크를 역순으로 설정(current->next = previous).
   • previous를 current로 이동(previous = current).
   • current를 next로 이동(current = next).
3. 루프가 끝나면 previous가 역순 리스트의 새 헤드가 됩니다.

시간 복잡도 : O(n) - 리스트를 한 번 순회하며, n은 노드 수입니다.

공간 복잡도 : O(1) - 세 개의 포인터만 사용하므로 상수 공간을 사용합니다.

C 코드:

#include 
#include 

struct Node {
    int data;
    struct Node* next;
};

// 반복적 역순 함수
struct Node* reverseIterative(struct Node* head) {
    struct Node* previous = NULL;
    struct Node* current = head;
    struct Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;      // 다음 노드 저장
        current->next = previous;  // 링크 역순으로 변경
        previous = current;        // previous 이동
        current = next;            // current 이동
    }
    
    return previous; // 새 헤드 반환
}

예제:

• 입력: 1 -> 2 -> 3 -> 4 -> NULL
• 출력: 4 -> 3 -> 2 -> 1 -> NULL

3. 재귀적 방법

재귀적 방법은 재귀를 활용하여 리스트를 역순으로 만듭니다. 리스트의 두 번째 노드부터 시작하는 서브리스트를 재귀적으로 역순으로 만든 후 링크를 조정합니다.

단계:

1. 리스트가 비어 있거나(head가 NULL) 노드가 하나뿐이면(head->next가 NULL), head를 반환합니다.
2. head->next부터 시작하는 서브리스트를 재귀적으로 역순으로 만듭니다:
   • rest_head = reverseRecursive(head->next)를 호출.
   • rest_head는 역순된 서브리스트의 새 헤드입니다.
3. 링크를 조정:
   • head->next->next = head를 설정하여 head를 역순된 서브리스트의 마지막 노드로 만듭니다.
   • head->next = NULL를 설정하여 head가 마지막 노드가 되도록 합니다.
4. 전체 역순 리스트의 새 헤드인 rest_head를 반환합니다.

시간 복잡도 : O(n) -  각 노드를 한 번씩 처리합니다.

공간 복잡도 : O(n) -  재귀 스택이 최대 n단계까지 쌓일 수 있습니다.

C 코드:

#include 
#include 

struct Node {
    int data;
    struct Node* next;
};

// 재귀적 역순 함수
struct Node* reverseRecursive(struct Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    struct Node* rest_head = reverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    
    return rest_head; // 새 헤드 반환
}

예제:

• 입력: 1 -> 2 -> 3 -> 4 -> NULL
• 출력: 4 -> 3 -> 2 -> 1 -> NULL

4. 반복적 방법과 재귀적 방법 비교

두 방법을 살펴본 후, 주요 차이점을 비교해 보겠습니다:

항목	반복적 방법	재귀적 방법
접근 방식	세 개의 포인터를 사용하여 링크를 반복적으로 역순으로 변경.	재귀를 사용하여 서브리스트를 역순으로 만들고 링크를 조정.
시간 복잡도	O(n)	O(n)
공간 복잡도	O(1) (상수 공간)	O(n) (재귀 스택)
이해의 용이성	포인터 조작으로 인해 처음에는 약간 복잡할 수 있음.	"분할 정복" 전략을 따르므로 직관적일 수 있음.
사용 사례	매우 긴 리스트에서 스택 오버플로우를 피하고자 할 때 적합.	리스트가 짧거나 재귀가 선호되는 경우 적합.

주요 차이점:

• 공간 사용: 반복적 방법은 O(1)로 공간 효율이 높습니다. 재귀적 방법은 재귀 스택으로 인해 O(n) 공간을 사용합니다.
• 스택 오버헤드: 재귀적 방법은 매우 긴 리스트에서 스택 오버플로우를 일으킬 수 있지만, 반복적 방법은 이 문제가 없습니다.
• 개념적 단순성: 재귀적 방법은 재귀에 익숙한 사람들에게 더 직관적이며, 문제를 더 작은 하위 문제로 나눕니다. 반복적 방법은 포인터를 신중히 다뤄야 합니다.

5. 결론

단일 연결 리스트를 역순으로 만드는 데는 반복적 방법과 재귀적 방법 모두 사용할 수 있습니다. 두 방법 모두 시간 복잡도는 O(n)로 동일하지만, 공간 사용에서 큰 차이가 있습니다. 반복적 방법은 O(1) 공간 복잡도로 더 효율적이며, 긴 리스트에 적합합니다. 반면, 재귀적 방법은 코드가 간결하고 이해하기 쉬운 경우가 많습니다.

두 방법을 선택할 때는 다음을 고려하세요:

• 반복적 방법은 공간 효율이 중요하거나 스택 오버플로우를 피해야 할 때 사용하세요.
• 재귀적 방법은 구현의 단순함이 우선이고 리스트 크기가 크지 않을 때 사용하세요.

두 방법 모두 알고리즘 설계에서 서로 다른 문제 해결 방식을 보여주므로, 둘 다 이해하는 것이 중요합니다.

참고 자료

• GeeksforGeeks - Reverse a Linked List
• InterviewBit - Reverse a Linked List
• DigitalOcean - Reverse a Linked List