단일 연결 리스트(Singly Linked List)가 입력으로 주어졌을 때, 목표는 원본 리스트의 노드를 하나씩 교대로 가져가는 두 개의 단일 연결 리스트로 분할하는 것입니다. 예를 들어 입력 리스트가 a → b → c → d → e → f라면, 분할 후 생성되는 두 개의 하위 리스트는 각각 a → c → e와 b → d → f가 됩니다.
이 문제는 두 개의 포인터 N1과 N2를 사용해 해결할 수 있습니다. 하나는 원본 리스트의 헤드(head)를 가리키고, 다른 하나는 head->next를 가리킵니다. 이후 두 포인터를 각각 다다음 노드(next of next)로 이동시키면서 하위 리스트를 구성합니다.
예제
입력 − 리스트 : 1 → 5 → 7 → 12 → 2 → 96 → 33
출력 −
원본 리스트 : 1 5 7 12 2 96 33
List 1: 1 7 2 33
List 2: 5 12 96
설명 − 1과 5에서 시작해 서로 교대되는 노드를 차례로 연결하면 위와 같은 두 개의 하위 리스트가 만들어집니다.
입력 − 리스트 : 13 → 53 → 90 → 18 → 44 → 11 → 99 → 32
출력 −
원본 리스트 : 13 53 90 18 44 11 99 32
List 1: 13 90 44 99
List 2: 53 18 11 32
설명 − 13과 53에서 시작해 교대 노드를 연결하여 위와 같은 하위 리스트를 생성합니다.
프로그램에 적용된 접근 방식
이 접근 방식에서는 두 포인터 N1과 N2를 사용합니다. 하나는 원본 리스트의 헤드를, 다른 하나는 head->next를 가리키며, 두 포인터를 다다음 노드로 이동시키면서 하위 리스트를 만듭니다.
int형 데이터 멤버와 next 포인터를 가지는 Node 구조체를 정의합니다.
addtohead(Node** head, int data) 함수는 새 노드를 리스트의 맨 앞에 추가하여 단일 연결 리스트를 만드는 데 사용됩니다.
위 함수를 이용해 첫 번째 노드를 가리키는 head 포인터와 함께 단일 연결 리스트를 생성합니다.
display(Node* head) 함수는 헤드 노드부터 시작해 연결 리스트 전체를 출력합니다.
두 개의 Node 포인터 node1과 node2를 선언합니다.
splitList(Node* head, Node** n1, Node** n2) 함수는 n1을 head로, n2를 head->next로 설정한 뒤 내부적으로 split(*n1, *n2)를 호출해 원본 리스트를 두 개의 하위 리스트로 분할합니다.
split(Node* N1, Node* N2) 함수는 N1과 N2 포인터를 받아 원본 리스트의 교대 노드들로 구성된 두 개의 하위 리스트를 만듭니다.
N1과 N2가 모두 NULL이면 아무 작업 없이 반환합니다.
N1->next가 NULL이 아니면 tmp = N1->next->next로 설정하고 N1->next = tmp로 갱신합니다.
N2->next가 NULL이 아니면 tmp = N2->next->next로 설정하고 N2->next = tmp로 갱신합니다.
다음 반복을 위해 split(N1->next, N2->next)를 재귀적으로 호출합니다.
마지막으로 display()를 사용해 두 하위 리스트를 출력합니다.
복잡도 분석
이 알고리즘은 리스트의 각 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 다만 재귀 호출이 노드 수에 비례해 호출 스택을 사용하므로 공간 복잡도 역시 O(n)입니다. 따라서 리스트가 매우 긴 경우에는 반복문 기반 구현으로 변경하면 추가 공간 없이 O(1)의 공간 복잡도로 처리할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void addtohead(Node** head, int data){
Node* nodex = new Node;
nodex->data = data;
nodex->next = (*head);
(*head) = nodex;
}
void split(Node* N1, Node* N2){
Node *tmp;
if (N1 == NULL || N2 == NULL){
return;
}
if (N1->next != NULL){
tmp=N1->next->next;
N1->next = tmp;
}
if (N2->next != NULL){
tmp=N2->next->next;
N2->next = tmp;
}
split(N1->next, N2->next);
}
void splitList(Node* head, Node** n1, Node** n2){
*n1 = head;
*n2 = head->next;
split(*n1, *n2);
}
void display(Node* head){
Node* curr = head;
if (curr != NULL){
cout<<curr->data<<" ";
display(curr->next);
}
}
int main(){
Node* head = NULL;
Node *node1 = NULL, *node2 = NULL;
addtohead(&head, 20);
addtohead(&head, 12);
addtohead(&head, 15);
addtohead(&head, 8);
addtohead(&head, 10);
addtohead(&head, 4);
addtohead(&head, 5);
cout<<"Original List :"<<endl;
display(head);
splitList(head, &node1, &node2);
cout<<endl<<"List 1: ";
display(node1);
cout<<endl<<"List 2: ";
display(node2);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Original List : 5 4 10 8 15 12 20 List 1: 5 10 15 20 List 2: 4 8 12