单链表输出偶数元素和剩余元素

Question

【问题描述】编写程序，要求完成以下需求：
1.输入若干正整数，按从小到大次序建立1个带头结点单链表并输出该有序链表
2.程序中要求设计一个实现单链表分离算法的Split函数，将原单链表中值为偶数的结点分离出来形成一个新单链表，新单链表中头结点重新申请，其余结点来自原链表，分离后，原链表中只剩非偶数值所在结点
3.最后显示2个单链表，并在程序退出前销毁单链表。
要求Split算法时间复杂性达到O（n）,程序不可存在内存溢出。
【输入格式】:
若干正整数，0结束（0非链表元素）
【输出格式】:
每个单链表输出占一行，元素间用分隔符->分隔；初始单链表、剩余元素单链表、偶数元素单链表，共3行。
【输入样例】:
100 2 3 50 2 1 5 8 0
【输出样例】:
1->2->2->3->5->8->50->100
1->3->5
2->2->8->50->100

Answer 1

供参考：

#include <stdio.h>
#include <malloc.h>

typedef struct Node {// 链表节点结构
    int    data;
    struct Node* next;
}Node, * LinkList;
void destroyNodes(LinkList L)
{
    Node *pL = NULL;
    while(L){
        pL = L;
        L = pL->next;
        free(pL);
    }
}
void show(LinkList L)// 输出单链表
{
    if (L == NULL || L->next == NULL) return;
    Node* p = L->next;
    while (p) {
        printf(p == L->next ? "%d" : "->%d", p->data);
        p = p->next;
    }
    printf("\n");
}
void Split(LinkList L1, LinkList* L2)//单链表分离
{
    Node* p = NULL, * pL1 = L1, *pL2 = NULL;
    while (pL1->next) {
          if (pL1->next->data % 2 == 0) {
              if ((*L2) == NULL){
                  (*L2) = (Node*)malloc(sizeof(Node));
                  (*L2)->data = -1;
                  (*L2)->next = NULL;
                  pL2 = (*L2);
              }
              p = pL1->next;
              pL1->next = p->next;
              p->next = NULL;
              pL2->next = p;
              pL2 = p;
          }
          else{
              pL1 = pL1->next;
          }
    }
}
// 创建链表
void createListFromHead(LinkList* L)
{
    Node* pL;
    int n;
    (*L) = (Node*)malloc(sizeof(Node));// 创建头结点
    (*L)->data = -1;
    (*L)->next = NULL;
    while (1) { // 生成链表
        scanf("%d", &n);
        if (n == 0)  break;
        Node* p = (Node*)malloc(sizeof(Node));
        p->next = NULL;
        p->data = n;
        pL = (*L);
        while (pL->next && pL->next->data < p->data)
             pL = pL->next;
        p->next = pL->next;
        pL->next = p;
    }
}
int main()
{
    LinkList L1 = NULL, L2 = NULL;
    createListFromHead(&L1);
    show(L1);
    Split(L1, &L2);
    show(L1);
    show(L2);
    destroyNodes(L1);
    destroyNodes(L2);

    return 0;
}