ย้ายศูนย์ทั้งหมดไปหน้าสุดของลิงก์ลิสต์ใน C++

โจทย์

ได้รับลิงก์ลิสต์ที่มีจำนวนเต็มสุ่มและศูนย์ เราต้องย้ายศูนย์ทั้งหมดไปหน้าสุดของลิงก์ลิสต์ มาดูตัวอย่างกัน

อินพุต

3 -> 0 -> 1 -> 0 -> 0 -> 1 -> 0 -> 0 -> 3 -> NULL

เอาต์พุต

0->0->0->0->0->3->1->1->3->NULL

อัลกอริธึม

• กำหนดลิงก์ลิสต์
• คืนค่าถ้าลิงก์ลิสต์ว่างหรือมีโหนดเดียว
• กำหนดโหนดสองตัวด้วยโหนดที่สองและโหนดแรกตามลำดับเพื่อติดตามโหนดปัจจุบันและก่อนหน้า
• วนลูปผ่านลิงก์ลิสต์จนถึงท้ายสุด
  • ถ้าโหนดปัจจุบันเป็น 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