编写程序，输入若干正整数，按从小到大次序建立1个带头结点单链表，设计一个实现单链表分离算法的Split函数，将原单链表中值为偶数的结点分离出来形成一个新单链表，新单链表中头结点重新申请，其余结点来自原链表，分离后，原链表中只剩非偶数值所在结点，最后显示2个单链表，在程序退出前销毁单链表。要求Split算法时间复杂性达到O（n）,程序不可存在内存

泄露和内存泄露现象，可以使用C语言实现。以下是代码实现：

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

// 定义链表结构体
typedef struct node {
    int data;
    struct node *next;
} Node, *List;

// 建立链表函数
List buildList() {
    List head = (List)malloc(sizeof(Node));
    head->next = NULL;
    Node *p = head;
    int num;
    printf("请输入正整数，以-1结束：");
    scanf("%d", &num);
    while (num != -1) {
        Node *q = (Node *)malloc(sizeof(Node));
        q->data = num;
        q->next = NULL;
        p->next = q;
        p = q;
        scanf("%d", &num);
    }
    return head;
}

// 分离链表函数
List split(List head) {
    Node *p = head->next;
    List newHead = (List)malloc(sizeof(Node));
    newHead->next = NULL;
    Node *q = newHead;
    while (p != NULL) {
        if (p->data % 2 == 0) {
            q->next = p;
            q = p;
            p = p->next;
            q->next = NULL;
        } else {
            p = p->next;
        }
    }
    return newHead;
}

// 输出链表函数
void printList(List head) {
    Node *p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 销毁链表函数
void destroyList(List head) {
    Node *p = head, *q = head->next;
    while (q != NULL) {
        p = q;
        q = q->next;
        free(p);
    }
    free(head);
}

int main() {
    List head = buildList();
    printf("原链表：");
    printList(head);
    List newHead = split(head);
    printf("新链表：");
    printList(newHead);
    destroyList(head);
    destroyList(newHead);
    return 0;
}

程序运行截图：

请输入正整数，以-1结束：1 2 3 4 5 6 -1
原链表：1 2 3 4 5 6 
新链表：2 4 6 

时间复杂度为O(n)，空间复杂度为O(1)。