拆分一个链表为偶数链表和奇数链表

问题简述

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

代码实现

#include <stdio.h> #include <stdlib.h> #include <malloc.h> #define FLAG -1 //停止输入的标志 typedef struct Node { int data; struct Node * next; }LNode,*LinkList; void CreateLinkList(LinkList L); void show_List(LinkList L); LNode *Breakupthelist(LinkList La,int *A,int *B); void main() { LinkList La,Lb; int A = 0,B = 0; La = (LinkList)malloc(sizeof(LNode));//创建头结点 printf("创建单链表：\n"); CreateLinkList(La); printf("遍历单链表：\n"); show_List(La); printf("拆分链表：\n"); Lb = Breakupthelist(La,&A,&B);//A,B用来判断全是奇数或全是偶数的情况 if(A == 0)//全是偶数 { printf("偶数链：\n"); show_List(La); printf("奇数链为空！\n"); } else if(B == 0)//全是奇数 { printf("奇数链：\n"); show_List(Lb); printf("偶数链为空！\n"); } else { printf("偶数链：\n"); show_List(La); printf("奇数链：\n"); show_List(Lb); } } void CreateLinkList(LinkList L) //尾插法 输出是输入的正序 { LinkList s,r; int x; scanf("%d",&x); r = L; while(x != FLAG) { s = (LNode *)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; scanf("%d",&x); } r->next = NULL; } void show_List(LinkList L) { LinkList p = L->next; printf("%d",p->data); p = p ->next; while(p != NULL) { printf("->%d",p->data); p = p->next; } printf("\n"); } LNode *Breakupthelist(LinkList La,int *A,int *B) //返回奇数链表的头结点 { LinkList p,q,r;//r始终指向偶数链的尾部 LinkList Lb = (LinkList)malloc(sizeof(LNode)); p = La; q = Lb; r = La; p = p->next; while(p) { if(p->data % 2 != 0) //奇数 { q->next = p; p = p->next; r->next = p; q = q->next; *A = 1; } else { p = p->next; r = r->next; *B = 1; } } q->next = NULL; return Lb; }