รับรายการที่เชื่อมโยงด้วยจำนวนเต็มและศูนย์แบบสุ่ม เราต้องย้ายศูนย์ทั้งหมดไปที่ด้านหน้าของรายการที่เชื่อมโยง มาดูตัวอย่างกัน
ป้อนข้อมูล
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
