Description

請撰寫一支程式，用 Linked list 儲存一個數列，接著先把所有數值為奇數的先印出來，接著再把數值為偶數的印出來。

Please write a program to store a sequence of numbers using a linked list. First, print out all the odd numbers in the sequence, followed by all the even numbers.

Input

輸入包含多個數字，中間以空白隔開，直到輸入 0 時結束，0 不需要加到linked list中。

The input contains multiple numbers separated by spaces, and it ends with 0. The number 0 should not be added to the linked list.

Output

請先印出數列中的所有奇數，再印出數列中的所有偶數，數字間以空白隔開，最後一個數字後面一樣有一個空白。

Print out all the odd numbers in the sequence first, followed by all the even numbers. Numbers should be separated by spaces, and there should be a single space after the last number.

Sample Input 1

Sample Output 1

1 5 2 6 4 3 7 9 10 0

1 5 3 7 9 2 6 4 10

Sample Input 2

Sample Output 2

10 9 8 7 6 5 4 3 2 3 4 5 0

9 7 5 3 3 5 10 8 6 4 2 4

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node in the linked list
typedef struct node {
    int data;
    struct node *next;
} Node;

// Function to print all odd numbers in the linked list
void printOdd(Node *head) {
    Node *current = head;
    while (current != NULL) {
        if (current->data % 2 != 0) { // Check if the number is odd
            printf("%d ", current->data);
        }
        current = current->next; // Move to the next node
    }
}

// Function to print all even numbers in the linked list
void printEven(Node *head) {
    Node *current = head;
    while (current != NULL) {
        if (current->data % 2 == 0) { // Check if the number is even
            printf("%d ", current->data);
        }
        current = current->next; // Move to the next node
    }
}

int main() {
    int num;
    Node *head = NULL;
    Node *tail = NULL;
    
    // Read numbers and create the linked list
    while (1) {
        scanf("%d", &num);
        if (num == 0) // Stop when encountering 0
            break;
        
        // Create a new node
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = num;
        newNode->next = NULL;
        
        if (head == NULL) { // If the list is empty, set the new node as the head
            head = newNode;
            tail = newNode;
        } else { // Otherwise, link the new node to the end of the list
            tail->next = newNode;
            tail = newNode;
        }
    }
    
    // Print odd numbers first
    printOdd(head);
    
    // Print even numbers
    printEven(head);
    
    printf("\\n"); // Print a newline at the end
    
    // Free memory
    Node *current = head;
    while (current != NULL) {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
    
    return 0;
}