C++로 주어진 크기 k의 그룹 단위로 연결 리스트 뒤집기

문제 개요

이 글에서는 단일 연결 리스트(singly linked list)가 주어졌을 때, 이를 주어진 크기 k의 그룹 단위로 뒤집는 방법을 다룹니다. 예를 들어 다음과 같습니다.

입력: 1->2->3->4->5->6->7->8->NULL, K = 3
출력: 3->2->1->6->5->4->8->7->NULL

입력: 1->2->3->4->5->6->7->8->NULL, K = 5
출력: 5->4->3->2->1->8->7->6->NULL

이 문제를 해결하는 한 가지 방법은 리스트를 순회하다가 부분 리스트의 크기가 k에 도달하면 해당 구간을 뒤집고, 이 과정을 리스트 끝까지 반복하는 것입니다.

해결 접근 방식

이 방식에서는 리스트를 순회하면서 부분 리스트에 포함된 노드의 개수를 세는 카운터를 유지합니다. 카운터가 k에 도달하면 해당 구간을 뒤집고, 남은 노드에 대해 같은 작업을 반복합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
class Node {
    public:
    int data;
    Node* next;
};
Node* reverse(Node* head, int k) {
    if (!head)
        return NULL;
    Node* curr = head;
    Node* next = NULL;
    Node* prev = NULL;
    int count = 0;
    while (curr != NULL && count < k) { // 카운트가 k보다 작은 동안 리스트를 뒤집습니다
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
        count++;
    }
    if (next != NULL) // 리스트가 아직 끝나지 않았다면 reverse 함수를 재귀 호출합니다
        head->next = reverse(next, k);
    return prev;
}
void push(Node** head_ref, int new_data) { // 리스트에 데이터를 추가하는 함수
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
void printList(Node* node) { // 연결 리스트를 출력하는 함수
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << "\n";
}
int main() {
    Node* head = NULL;
    int k = 3; // 주어진 k 값
    push(&head, 8);
    push(&head, 7);
    push(&head, 6);
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    cout << "원본 리스트 \n";
    printList(head);
    head = reverse(head, k); // 이 함수는 새로운 head를 반환합니다
    cout << "새 리스트 \n";
    printList(head);
    return (0);
}

실행 결과

원본 리스트
1 2 3 4 5 6 7 8
새 리스트
3 2 1 6 5 4 8 7

위 접근 방식의 시간 복잡도는 O(N)이며, 여기서 N은 주어진 리스트의 크기입니다. 이 방법은 재귀를 기반으로 동작하기 때문에 제약 조건이 큰 입력에서도 안정적으로 사용할 수 있습니다.

코드 설명

이 접근 방식에서는 리스트를 순회하면서 카운터 변수가 k보다 작은 동안 계속 노드의 연결 방향을 뒤집습니다. 카운터가 k에 도달하면 재귀 호출을 통해 다음 부분 리스트의 뒤집기를 진행하고, 현재 부분 리스트의 마지막 노드를 다음에 뒤집힌 부분 리스트의 첫 번째 노드와 연결합니다. 이러한 그룹 간 연결 작업은 재귀(recursion)를 통해 자연스럽게 처리됩니다.

마무리

이 글에서는 재귀를 활용해 주어진 크기의 그룹 단위로 연결 리스트를 뒤집는 문제를 해결했습니다. 문제 해결을 위한 전체적인 접근 방식과 C++ 구현 코드, 실행 결과까지 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 쉽게 옮겨 구현할 수 있습니다. 이 글이 여러분에게 도움이 되기를 바랍니다.