c语言：设计一个算法，将一个结点值为自然数的单链表拆分为两个单链表，原表中保留值为偶数的结点，而值为奇数的结点按他们在原表中的相对次序组成一个新的单链表

以下是C语言的代码实现：

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

//定义链表结点结构体
struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* createList(int arr[], int n) {
    struct ListNode *head, *p, *q;
    head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;
    p = head;
    for (int i = 0; i < n; i++) {
        q = (struct ListNode*)malloc(sizeof(struct ListNode));
        q->val = arr[i];
        q->next = NULL;
        p->next = q;
        p = q;
    }
    return head;
}

void printList(struct ListNode* head) {
    struct ListNode* p = head->next;
    while (p) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

struct ListNode* splitList(struct ListNode* head) {
    struct ListNode *evenHead, *oddHead, *p, *q;
    evenHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    oddHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    evenHead->next = NULL;
    oddHead->next = NULL;
    p = evenHead;
    q = oddHead;
    struct ListNode* cur = head->next;
    while (cur) {
        if (cur->val % 2 == 0) {
            p->next = cur;
            p = cur;
        } else {
            q->next = cur;
            q = cur;
        }
        cur = cur->next;
    }
    p->next = NULL;
    q->next = NULL;
    head->next = evenHead->next;
    return oddHead;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(int);
    struct ListNode* head = createList(arr, n);
    printf("Original list: ");
    printList(head);
    struct ListNode* oddHead = splitList(head);
    printf("Even list: ");
    printList(head);
    printf("Odd list: ");
    printList(oddHead);
    return 0;
}

这个算法的实现思路是：遍历原链表，将偶数结点连接到一个新的链表上，将奇数结点连接到另一个新的链表上。最后，将原链表的表头指向偶数链表的表头，返回奇数链表的表头。

注意，这个算法需要手动创建两个新的链表，分别保存偶数结点和奇数结点。最后，由于原链表的表头改变了，需要将原链表的表头指向偶数链表的表头。