이 튜토리얼에서는 연결 리스트(Linked List)가 주어졌을 때, x보다 작은 값들은 모두 리스트 앞쪽에 배치하고 나머지 값들은 뒤쪽에 배치하는 문제를 다룹니다. 중요한 조건은 각 요소의 원래 상대적 순서를 그대로 유지해야 한다는 점입니다.
문제 예시
입력 : 1->4->3->2->5->2->3, x = 3 출력 : 1->2->2->3->3->4->5 입력 : 1->4->2->10 x = 3 출력 : 1->2->4->10 입력 : 10->4->20->10->3 x = 3 출력 : 3->10->4->20->10
해결 접근 방식
이 문제를 해결하기 위해서는 세 개의 연결 리스트를 만드는 것이 핵심입니다.
- x보다 작은 값을 만나면 첫 번째 리스트(small)에 삽입합니다.
- x와 같은 값은 두 번째 리스트(equal)에 삽입합니다.
- x보다 큰 값은 세 번째 리스트(large)에 삽입합니다.
각 리스트는 원래 순서대로 노드를 추가하므로 상대적 순서가 자연스럽게 보존됩니다. 마지막에는 세 개의 리스트를 small → equal → large 순서로 연결(concatenate)하여 최종 리스트를 만들면 됩니다.
C++ 구현 코드
#include<bits/stdc++.h>
using namespace std;
struct Node{ // 노드 구조체 정의
int data;
struct Node* next;
};
// 새 노드를 생성하는 유틸리티 함수
Node *newNode(int data){
struct Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
struct Node *partition(struct Node *head, int x){
struct Node *smallhead = NULL, *smalllast = NULL; // 리스트의 머리와 꼬리 포인터 두 개를 사용하면
// 마지막 연결 작업이 쉬워집니다
struct Node *largelast = NULL, *largehead = NULL;
struct Node *equalhead = NULL, *equallast = NULL;
while (head != NULL){ // 원본 리스트 순회
if (head->data == x){ // x와 같은 경우
if (equalhead == NULL)
equalhead = equallast = head;
else{
equallast->next = head;
equallast = equallast->next;
}
}
else if (head->data < x){ // x보다 작은 경우
if (smallhead == NULL)
smalllast = smallhead = head;
else{
smalllast->next = head;
smalllast = head;
}
}
else{ // x보다 큰 경우
if (largehead == NULL)
largelast = largehead = head;
else{
largelast->next = head;
largelast = head;
}
}
head = head->next;
}
if (largelast != NULL) // 마지막 리스트의 끝이므로 NULL을 가리키도록 설정
largelast->next = NULL;
/**********리스트 연결**********/
if (smallhead == NULL){
if (equalhead == NULL)
return largehead;
equallast->next = largehead;
return equalhead;
}
if (equalhead == NULL){
smalllast->next = largehead;
return smallhead;
}
smalllast->next = equalhead;
equallast->next = largehead;
return smallhead;
}
void printList(struct Node *head){ // 리스트 출력 함수
struct Node *temp = head;
while (temp != NULL){
printf("%d ", temp->data);
temp = temp->next;
}
}
int main(){
struct Node* head = newNode(10);
head->next = newNode(4);
head->next->next = newNode(5);
head->next->next->next = newNode(30);
head->next->next->next->next = newNode(2);
head->next->next->next->next->next = newNode(50);
int x = 3;
head = partition(head, x);
printList(head);
return 0;
}실행 결과
2 10 4 5 30
코드 설명
위 코드에서는 각 리스트의 머리(head)와 꼬리(tail) 포인터를 함께 관리하는 것이 핵심입니다. 머리 포인터는 최종적으로 반환할 시작점을 저장하고, 꼬리 포인터는 새 노드를 계속 추가할 수 있게 해줍니다.
순회가 끝난 후에는 세 가지 경우를 모두 고려해야 합니다.
- small 리스트가 비어 있는 경우 — equal 또는 large 리스트의 머리를 반환합니다.
- equal 리스트가 비어 있는 경우 — small과 large를 직접 연결합니다.
- 세 리스트 모두 존재하는 경우 — small → equal → large 순서로 연결합니다.
또한 마지막 리스트(large)의 꼬리 노드는 반드시 NULL을 가리키도록 처리해야 합니다. 그렇지 않으면 이전 노드들이 남긴 잘못된 next 포인터 때문에 리스트가 오염되거나 무한 루프가 발생할 수 있습니다.
시간 복잡도
이 알고리즘은 원본 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 공간 없이 기존 노드들을 재배치하므로 공간 복잡도는 O(1)입니다. 매우 효율적인 방법입니다.
마무리
이 튜토리얼에서는 주어진 값을 기준으로 연결 리스트를 분할하면서 원래 순서를 유지하는 방법을 학습했습니다. C++ 코드와 함께 전체적인 접근 방식도 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 코딩 문제 해결에 도움이 되기를 바랍니다.