C++에서 연결 리스트를 분리하는 방법: 홀수·짝수 인덱스 노드 구분하기

연결 리스트란?

연결 리스트(Linked List)는 각 노드가 두 개의 블록으로 구성되는 선형 자료구조입니다. 한 블록에는 노드의 값(데이터)이 저장되고, 다른 블록에는 다음 노드의 주소가 저장됩니다.

각 노드가 데이터와 다음 노드를 가리키는 포인터를 담고 있는 연결 리스트가 있다고 가정해 보겠습니다. 이때 과제는 주어진 연결 리스트를 분리(segregate)하는 것입니다. 여기서 분리란 리스트 안에서 홀수 인덱스에 있는 노드들과 짝수 인덱스에 있는 노드들을 나누어 재배치하는 작업을 의미합니다.

문제 해결 접근 방식

주어진 연결 리스트를 분리하려면 홀수 인덱스를 추적하는 포인터, 짝수 인덱스를 추적하는 포인터, 그리고 짝수 인덱스 노드들의 시작 위치를 기억하는 포인터, 총 세 개의 포인터를 사용합니다. 이후 전체 연결 리스트를 한 번 순회하면서 각 포인터를 적절히 연결해 주면 됩니다.

연결 리스트의 인덱스는 '1'부터 시작합니다. 따라서 리스트의 첫 번째 노드는 항상 홀수 인덱스 노드로 취급되며, 그다음 노드는 짝수 인덱스 노드로 취급됩니다.

알고리즘 단계

• 데이터와 다음 노드를 가리키는 포인터를 가진 연결 리스트를 준비합니다.
• segregateList(listnode *head) 함수는 헤드 노드의 포인터를 입력받아 분리된 연결 리스트를 반환합니다.
• 현재 리스트의 헤드를 가리키도록 oddIndex, evenIndex, evenHead 세 개의 포인터를 초기화합니다.
• 전체 리스트를 순회하면서 oddIndex->next를 evenIndex->next로 연결하여 홀수 노드들을 이어 줍니다.
• 같은 방식으로 evenIndex->next를 oddIndex->next로 연결하여 짝수 노드들을 이어 줍니다.
• 순회가 끝나면 홀수 리스트의 마지막 노드를 짝수 리스트의 머리(evenHead)에 연결한 뒤 헤드 포인터를 반환합니다.

C++ 구현 예제

#include <iostream>
using namespace std;
class node {
    public:
        int data;
    node * next;
    node(int d) {
        data = d;
        next = NULL;
    }
};
node * segregateList(node * head) {
    if (head == NULL) {
        return NULL;
    }
    node * oddIndex = head;
    node * evenIndex = head -> next;
    node * evenHead = evenIndex;
    while (evenIndex != NULL and evenIndex -> next != NULL) {
        oddIndex -> next = evenIndex -> next;
        oddIndex = oddIndex -> next;
        evenIndex -> next = oddIndex -> next;
        evenIndex = evenIndex -> next;
    }
    oddIndex -> next = evenHead;
    return head;
}
void insertAtNode(node * & head, int data) {
    node * n = new node(data);
    n -> next = head;
    head = n;
}
void print(node * head) {
    while (head != NULL) {
        cout << head -> data << "->";
        head = head -> next;
    }
}
int main() {
    node * head = NULL;
    // 헤드 노드에 NULL 값이 들어 있을 수도 있습니다.
    insertAtNode(head, 5);
    insertAtNode(head, 8);
    insertAtNode(head, 3);
    insertAtNode(head, 1);
    insertAtNode(head, 2);
    print(head);
    cout << endl;
    segregateList(head);
    print(head);
}

출력 결과

2->3->5->1->8->

입력으로 주어진 연결 리스트는 2->1->3->8->5->입니다. 이 리스트를 분리하면 홀수 인덱스 노드(2, 3, 5)가 앞쪽에, 짝수 인덱스 노드(1, 8)가 뒤쪽에 배치되어 최종적으로 2->3->5->1->8->이 출력됩니다.

복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 새로운 노드를 생성하지 않고 기존 노드의 포인터만 재연결하기 때문에 공간 복잡도는 O(1)로 매우 효율적입니다.