정수와 0이 무작위로 섞여 있는 연결 리스트가 주어졌을 때, 리스트에 포함된 모든 0을 앞쪽으로 이동시키는 것이 이번 문제의 목표입니다. 먼저 예시를 통해 문제를 살펴보겠습니다.
입력
3 -> 0 -> 1 -> 0 -> 0 -> 1 -> 0 -> 0 -> 3 -> NULL
출력
0 -> 0 -> 0 -> 0 -> 0 -> 3 -> 1 -> 1 -> 3 -> NULL
출력 결과를 보면 0이 아닌 노드들의 상대적인 순서는 그대로 유지되면서, 모든 0이 리스트의 맨 앞으로 이동한 것을 확인할 수 있습니다.
알고리즘
이 문제는 각 노드를 순회하면서 값이 0인 노드를 발견하면 해당 노드를 리스트의 맨 앞(헤드)으로 옮기는 방식으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- 연결 리스트를 초기화합니다.
- 연결 리스트가 비어 있거나 노드가 하나뿐이라면 그대로 반환합니다.
- 현재 노드와 이전 노드를 추적하기 위해 두 개의 포인터를 준비합니다. 현재 노드는 두 번째 노드로, 이전 노드는 첫 번째 노드(헤드)로 초기화합니다.
- 연결 리스트의 끝에 도달할 때까지 순회합니다.
- 순회 중 다음 작업을 수행합니다.
- 현재 노드의 값이 0이라면, 해당 노드를 새로운 헤드로 만듭니다.
- 이전 노드의 next 포인터가 현재 노드의 다음 노드를 가리키도록 연결을 재조정하여 0 노드를 기존 위치에서 제거합니다.
- 제거한 노드의 next가 기존 헤드를 가리키도록 설정한 뒤, 해당 노드를 새로운 헤드로 지정합니다.
- 현재 노드와 이전 노드 변수의 값을 갱신합니다.
구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *next;
};
void addNewNode(struct Node **head, int data) {
struct Node *newNode = new Node;
newNode->data = data;
newNode->next = *head;
*head = newNode;
}
void moveZeroes(struct Node **head) {
if (*head == NULL) {
return;
}
struct Node *temp = (*head)->next, *prev = *head;
while (temp != NULL) {
if (temp->data == 0) {
Node *current = temp;
temp = temp->next;
prev->next = temp;
current->next = *head;
*head = current;
} else {
prev = temp;
temp = temp->next;
}
}
}
void printLinkedList(struct Node *head) {
while (head != NULL) {
cout << head->data << "->";
head = head->next;
}
cout << "NULL" << endl;
}
int main() {
struct Node *head = NULL;
addNewNode(&head, 3);
addNewNode(&head, 0);
addNewNode(&head, 1);
addNewNode(&head, 0);
addNewNode(&head, 0);
addNewNode(&head, 1);
addNewNode(&head, 0);
addNewNode(&head, 0);
addNewNode(&head, 3);
moveZeroes(&head);
printLinkedList(head);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
0->0->0->0->0->3->1->1->3->NULL
복잡도 분석
시간 복잡도: 연결 리스트의 모든 노드를 한 번씩만 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 리스트의 노드 개수입니다.
공간 복잡도: 추가적인 자료구조 없이 포인터 몇 개만 사용하므로 공간 복잡도는 O(1)입니다.
이 알고리즘의 핵심은 0을 만났을 때 해당 노드를 리스트에서 분리한 후 헤드 앞에 다시 연결하는 것입니다. 이때 이전 노드(prev)의 next 포인터를 반드시 갱신해야 리스트의 연결이 끊기지 않는다는 점에 유의하세요.