임의의 정수와 0이 있는 연결 목록이 제공됩니다. 모든 0을 연결 목록의 맨 앞으로 이동해야 합니다. 예를 들어 보겠습니다.
입력
3 -> 0 -> 1-> 0 -> 0 -> 1 -> 0 -> 0 -> 3 -> NULL
출력
0->0->0->0->0->3->1->1->3->NULL
알고리즘
- 연결 목록을 초기화합니다.
- 연결 목록이 비어 있거나 단일 노드가 있는 경우 반환합니다.
- 현재 및 이전 노드를 추적하기 위해 각각 두 번째 노드와 첫 번째 노드로 두 개의 노드를 초기화합니다.
- 끝에 도달할 때까지 연결 목록을 반복합니다.
-
- 현재 노드가 0이면 새 헤드로 만듭니다.
- 현재 및 이전 노드 변수의 값을 업데이트합니다.
- 노드를 새 헤드로 만들면 노드가 앞으로 이동합니다.
- 새 헤드의 다음 값을 이전 헤드로 업데이트합니다.
구현
다음은 위의 알고리즘을 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