class Node {
public:
    long long data;
    Node* next;
    Node(long long data) : data(data), next(nullptr) {}
};

void radix_sort_linked_list(std::vector<long long>& arr, long long size) {
    Node** least_sig_digit = new Node*[size]();
    Node** least_sig_digit_last = new Node*[size]();
    for (long long num : arr) {
        long long q = num / size;
        long long r = num % size;
        if (least_sig_digit[r] == nullptr) {
            least_sig_digit[r] = new Node(q);
            least_sig_digit_last[r] = least_sig_digit[r];
        } else {
            least_sig_digit_last[r]->next = new Node(q);
            least_sig_digit_last[r] = least_sig_digit_last[r]->next;
        }
    }
    Node** highest_sig_digit = new Node*[size]();
    Node** highest_sig_digit_last = new Node*[size]();
    for (long long k = 0; k < size; ++k) {
        Node* current = least_sig_digit[k];
        while (current != nullptr) {
            long long q = current->data;
            if (highest_sig_digit[q] == nullptr) {
                highest_sig_digit[q] = new Node(q * size + k);
                highest_sig_digit_last[q] = highest_sig_digit[q];
            } else {
                highest_sig_digit_last[q]->next = new Node(q * size + k);
                highest_sig_digit_last[q] = highest_sig_digit_last[q]->next;
            }
            current = current->next;
        }
    }
    long long i = 0;
    for (long long k = 0; k < size; ++k) {
        Node* current = highest_sig_digit[k];
        while (current != nullptr) {
            arr[i++] = current->data;
            current = current->next;
        }
    }

    // Free memory
    for (long long k = 0; k < size; ++k) {
        Node* current = least_sig_digit[k];
        while (current != nullptr) {
            Node* temp = current;
            current = current->next;
            delete temp;
        }
    }
    for (long long k = 0; k < size; ++k) {
        Node *current = highest_sig_digit[k];
        while (current != nullptr) {
            Node *temp = current;
            current = current->next;
            delete temp;
        }
    }
    delete[] least_sig_digit;
    delete[] least_sig_digit_last;
    delete[] highest_sig_digit;
    delete[] highest_sig_digit_last;
}