think: 1顺序建立链表+链表内元素的插入操作+链表内元素的最优解情况判断+链表内元素的顺序输出
sdut原题链接
数据结构实验之链表五：单链表的拆分 Time Limit: 1000MS Memory Limit: 65536KB
Problem Description 输入N个整数顺序建立一个单链表，将该单链表拆分成两个子链表，第一个子链表存放了所有的偶数，第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。
Input 第一行输入整数N;； 第二行依次输入N个整数。
Output 第一行分别输出偶数链表与奇数链表的元素个数； 第二行依次输出偶数子链表的所有数据； 第三行依次输出奇数子链表的所有数据。
Example Input 10 1 3 22 8 15 999 9 44 6 1001
Example Output 4 6 22 8 44 6 1 3 15 999 9 1001
Hint 不得使用数组！
Author
以下为accepted代码
#include <stdio.h> #include <stdlib.h> int cnt1, cnt2; struct node { int Data; struct node *next; }*head, *tail; void Build(int n);//顺序建立链表 void Sep_ans(struct node *h);//链表的拆分和新链表元素的顺序输出 struct node * Insert(struct node *tail, int x);//链表元素的插入 void Pri(struct node *h);//顺序输出链表 int main() { int n; while(scanf("%d", &n) != EOF) { cnt1 = cnt2 = 0; head = (struct node *)malloc(sizeof(struct node)); head->next = NULL; tail = head; Build(n); Sep_ans(head); } return 0; } void Build(int n)//顺序建立链表 { struct node *p; for(int i = 0; i < n; i++) { p = (struct node *)malloc(sizeof(struct node)); scanf("%d", &p->Data); p->next = tail->next; tail->next = p; tail = p; } } void Pri(struct node *h)//链表内元素的顺序输出 { struct node *p; p = h->next; while(p != NULL) { printf("%d%c", p->Data, p->next == NULL? '\n': ' '); p = p->next; } } struct node * Insert(struct node *Tail, int x)//链表内元素的插入 { struct node *p; p = (struct node *)malloc(sizeof(struct node)); p->Data = x; p->next = Tail->next; Tail->next = p; Tail = p; return Tail; } void Sep_ans(struct node *h)//链表的拆分和新链表元素的顺序输出 { struct node *head1, *head2, *tail1, *tail2; head1 = (struct node *)malloc(sizeof(struct node)); head1->next = NULL; tail1 = head1; head2 = (struct node *)malloc(sizeof(struct node)); head2->next = NULL; tail2 = head2; struct node *p; p = h->next; while(p != NULL) { if(p->Data % 2 == 0) { cnt1++; tail1 = Insert(tail1, p->Data); } else { cnt2++; tail2 = Insert(tail2, p->Data); } p = p->next; } printf("%d %d\n", cnt1, cnt2); Pri(head1); Pri(head2); } /*************************************************** User name: Result: Accepted Take time: 0ms Take Memory: 104KB Submit time: 2017-03-10 17:56:27 ****************************************************/