Di chuyển tất cả số 0 về đầu linked list C++

Cho danh sách liên kết chứa các số nguyên và 0. Di chuyển tất cả nút giá trị 0 lên đầu danh sách, giữ thứ tự tương đối của các phần tử khác.

Ví dụ

Input: 3→0→1→0→0→1→0→0→3→NULL
Output: 0→0→0→0→0→3→1→1→3→NULL

Thuật toán

• Duyệt danh sách với hai con trỏ prev, curr.
• Nếu curr->data == 0:
  • Tách curr ra: prev->next = curr->next.
  • Chèn curr lên đầu: curr->next = head; head = curr.
  • Cập nhật curr = prev->next.
• Ngược lại: tiến prev = curr; curr = curr->next.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

struct Node { int data; Node* next; };

void push(Node** head, int data) {
    Node* n = new Node{data, *head};
    *head = n;
}

void moveZerosToFront(Node** head) {
    if (!*head) return;
    Node *prev = *head, *curr = (*head)->next;
    while (curr) {
        if (curr->data == 0) {
            prev->next = curr->next;
            curr->next = *head;
            *head = curr;
            curr = prev->next;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
}

void printList(Node* head) {
    while (head) { cout << head->data << "->"; head = head->next; }
    cout << "NULL" << endl;
}

int main() {
    Node* head = nullptr;
    int vals[] = {3,0,1,0,0,1,0,0,3};
    for (int i = 8; i >= 0; i--) push(&head, vals[i]);
    moveZerosToFront(&head);
    printList(head);
    return 0;
}

Kết quả

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