Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 단일 연결 리스트에서 K개 노드씩 번갈아 가며 역순으로 뒤집는 방법

이 튜토리얼에서는 길이가 N인 연결 리스트 A와 정수 K가 주어졌을 때, 크기가 K인 노드 그룹들을 번갈아 가며 역순으로 뒤집는 문제를 다룹니다. 여기서 N은 K로 나누어떨어진다는 조건이 있습니다. 함수의 첫 번째 인자는 연결 리스트 A의 헤드 포인터이고, 두 번째 인자는 정수 K입니다.

입력 예시

5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null, K = 2

출력

6 -> 5 -> 2 -> 8 -> 2 -> 5 -> 4 -> 8 -> 6 -> 9 -> null
1 -> 2 -> 5 -> 8 -> 9 -> 6 -> 4 -> 5 -> 8 -> null, K = 3

출력

5 -> 2 -> 1 -> 8 -> 9 -> 6 -> 8 -> 5 -> 4 -> null

위 예시에서 확인할 수 있듯이, 첫 번째 K개 노드 그룹은 뒤집히고, 다음 K개 노드 그룹은 원래 순서 그대로 유지되며, 이 패턴이 리스트 끝까지 반복됩니다.

반복(Iterative) 방식 접근법

  • 매 반복마다 2K개의 노드를 순회하면서, join 포인터와 tail 포인터를 활용해 각 K 노드 그룹의 시작 노드(머리)와 끝 노드(꼬리)를 기록합니다.

  • 그다음 해당 K개의 노드를 뒤집고, 뒤집힌 그룹의 마지막 노드를 join 포인터가 가리키는 이전 그룹과 연결합니다.

  • 현재 포인터(current)를 다음 K개 노드 위치로 이동시킵니다.

  • 유지되는 그룹의 마지막 노드가 새로운 tail이 되고, join 포인터는 다음에 뒤집힐 새 그룹의 머리를 가리키며 두 부분이 자연스럽게 병합됩니다. 리스트의 모든 노드가 처리될 때까지 이 과정을 반복합니다.

C++ 반복 방식 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Node {
    public:
    int data;
    Node* next;
};
Node* kAltReverse(struct Node* head, int k){
    Node* prev = NULL;
    Node* curr = head;
    Node* temp = NULL;
    Node* tail = NULL;
    Node* newHead = NULL;
    Node* join = NULL;
    int t = 0;
    while (curr) {
        t = k;
        join = curr;
        prev = NULL;
        while (curr && t--) {
            temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = temp;
        }
        if (!newHead)
            newHead = prev;
        if (tail)
            tail->next = prev;
        tail = join;
        tail->next = curr;
        t = k;
        while (curr && t--) {
            prev = curr;
            curr = curr->next;
        }
        tail = prev;
    }
    return newHead;
}
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){
    int count = 0;
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
        count++;
    }
}
int main(void){
    Node* head = NULL;
    int i;
    for (i = 6; i <27; i+=3)
        push(&head, i);
    int k = 3;
    cout << "Given linked list \n";
    printList(head);
    head = kAltReverse(head, k);
    cout << "\n Modified Linked list \n";
    printList(head);
    return (0);
}

실행 결과

Given linked list
24 21 18 15 12 9 6
Modified Linked list
18 21 24 15 12 9 6

실행 결과를 보면 앞의 3개 노드(24, 21, 18)는 18, 21, 24로 뒤집혔고, 다음 3개 노드(15, 12, 9)는 원래 순서를 그대로 유지하고, 마지막 노드 6은 그대로 남아 있는 것을 확인할 수 있습니다.

재귀(Recursive) 방식 접근법

  • 시작 지점부터 K개의 노드를 순회하고, temp 값을 K+1번째 노드로 설정합니다.

  • 순회한 K개의 노드 전체를 뒤집습니다.

  • 뒤집힌 그룹의 마지막 노드의 next 포인터를 temp가 가리키는 노드로 설정합니다.

  • 다음 K개 노드 그룹은 건너뛰고 포인터만 이동시킵니다.

  • 리스트의 마지막 노드에 도달할 때까지 위 과정을 재귀적으로 반복하여 다음 K개 노드를 뒤집습니다.

의사 코드(Pseudo Code)

reverseAltK(head, k)
    curr = head
    prev = null
    next = null
    count = 0
    WHILE count < k AND curr
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
        count = count + 1
IF head
    head.next = curr
count = 0
WHILE count < k-1 AND curr
    curr = curr.next
    count = count + 1
IF curr
    curr.next = reverseKGroupAltRecursive(curr.next, k)
return prev

C++ 재귀 방식 구현 예제

#include <bits/stdc++.h>
using namespace std;
/* 링크드 리스트 노드 */
class node{
    public:
    int data;
    node* next;
};
/* kAltReverse()의 헬퍼 함수 */
node * _kAltReverse(node *node, int k, bool b);

/* 주어진 연결 리스트를 크기 k 그룹 단위로
   번갈아 가며 뒤집는 함수 */
node *kAltReverse(node *head, int k){
    return _kAltReverse(head, k, true);
}
/* kAltReverse()의 헬퍼 함수.
   세 번째 매개변수 b가 true로 전달되면
   k개 노드만 뒤집고, false라면 포인터를
   k개 노드만큼 앞으로 이동한 뒤 재귀 호출 */
node * _kAltReverse(node *Node, int k, bool b){
    if(Node == NULL)
        return NULL;
    int count = 1;
    node *prev = NULL;
    node *current = Node;
    node *next;
    /* 이 루프는 두 가지 역할을 합니다.
       1) b가 true이면 k개 노드를 뒤집음
       2) b가 false이면 current 포인터만 이동 */
    while(current != NULL && count <= k){
        next = current->next;
        /* b가 true일 때만 노드를 뒤집음 */
            if(b == true)
                current->next = prev;
        prev = current;
        current = next;
        count++;
    }
    /* 3) b가 true이면 Node는 k번째 노드이므로,
       나머지 리스트를 Node 뒤에 연결함.
       4) 연결 후 새로운 head를 반환 */
    if(b == true){
        Node->next = _kAltReverse(current, k, !b);
        return prev;
    }
    /* b가 false이면 prev 뒤에 나머지 리스트를 연결 */
    else{
        prev->next = _kAltReverse(current, k, !b);
        return Node;
    }
}
/* 유틸리티 함수 */
/* 노드 추가(push) 함수 */
void push(node** head_ref, int new_data){
    /* 노드 할당 */
    node* new_node = new node();
    /* 데이터 저장 */
    new_node->data = new_data;
    /* 새 노드에 기존 리스트 연결 */
    new_node->next = (*head_ref);
    /* head를 새 노드로 이동 */
    (*head_ref) = new_node;
}
/* 연결 리스트 출력 함수 */
void printList(node *node){
    int count = 0;
    while(node != NULL){
        cout << node->data << " ";
        node = node->next;
        count++;
    }
}
// 드라이버 코드
int main(void){
    /* 빈 리스트로 시작 */
    node* head = NULL;
    int i;
    // 1->2->3->4->5...... ->20 리스트 생성
    for(i = 20; i > 0; i--)
        push(&head, i);
    cout << "Given linked list \n";
    printList(head);
    head = kAltReverse(head, 3);
    cout << "\nModified Linked list \n";
    printList(head);
    return(0);
}

실행 결과

Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Modified Linked list
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

출력 결과를 보면 1, 2, 3 → 3, 2, 1로 뒤집히고, 4, 5, 6은 그대로 유지되며, 7, 8, 9 → 9, 8, 7로 다시 뒤집히는 패턴이 리스트 전체에 걸쳐 번갈아 적용된 것을 확인할 수 있습니다.

마무리

이번 튜토리얼에서는 단일 연결 리스트에서 K개 노드씩 번갈아 가며 뒤집는 방법을 반복문 방식과 재귀 방식 두 가지로 살펴보았고, 의사 코드와 C++ 실제 구현 코드를 통해 동작 원리를 확인했습니다. 소개한 로직은 Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 작성할 수 있습니다. 재귀 방식은 코드가 간결하다는 장점이 있고, 반복 방식은 깊은 재귀 호출로 인한 스택 오버플로우 위험이 없다는 장점이 있으므로, 상황에 맞게 적절한 방식을 선택하시기 바랍니다. 이 튜토리얼이 여러분의 학습에 도움이 되기를 바랍니다.