【SDUT】【链表】2120 - 数据结构实验之链表五:单链表的拆分
程序员文章站
2022-06-15 17:44:58
Problem Description 输入N个整数顺序建立一个单链表,将该单链表拆分成两个子链表,第一个子链表存放了所有的偶数,第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。 Input 第一行输入整数N;;第二行依次输入N个整数。 Output 第一行分别输出偶数链表与奇 ......
problem description
输入n个整数顺序建立一个单链表,将该单链表拆分成两个子链表,第一个子链表存放了所有的偶数,第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。
input
第一行输入整数n;;
第二行依次输入n个整数。
第二行依次输入n个整数。
output
第一行分别输出偶数链表与奇数链表的元素个数;
第二行依次输出偶数子链表的所有数据;
第三行依次输出奇数子链表的所有数据。
第二行依次输出偶数子链表的所有数据;
第三行依次输出奇数子链表的所有数据。
sample input
10 1 3 22 8 15 999 9 44 6 1001
sample output
4 6 22 8 44 6 1 3 15 999 9 1001
hint
不得使用数组!
source
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 6 using namespace std; 7 8 struct node 9 { 10 int data; 11 struct node *next; 12 }; 13 14 int cnt1,cnt2; 15 16 //申请空间 17 struct node *arr_mal(struct node *p) 18 { 19 p = (struct node *)malloc(sizeof(struct node)); 20 return p; 21 } 22 23 //创建链表 24 void arr_create(struct node *head,int n) 25 { 26 struct node *p=null,*tail=null; 27 tail = head; 28 while(n--) 29 { 30 p = arr_mal(p); 31 scanf("%d",&p ->data); 32 tail ->next = p; 33 tail = tail ->next; 34 } 35 } 36 37 //输出链表 38 void arr_prin(struct node *head) 39 { 40 struct node *p=null; 41 p = head ->next; 42 if(p != null) 43 { 44 printf("%d",p ->data); 45 p = p ->next; 46 } 47 while(p != null) 48 { 49 printf(" %d",p ->data); 50 p = p ->next; 51 } 52 printf("\n"); 53 } 54 55 //拆分 56 void arr_split(struct node *head1,struct node *head2) 57 { 58 59 struct node *p1=null,*p2=null,*tail=null; 60 p1 = head1; 61 p2 = head2; 62 while(p1 ->next != null) 63 { 64 if(p1 ->next->data%2) 65 { 66 p1 = p1 ->next; 67 cnt1++; 68 } 69 else 70 { 71 tail = p1 ->next; 72 p1 ->next = tail ->next; 73 tail ->next = null; 74 p2 ->next = tail; 75 p2 = p2 ->next; 76 cnt2++; 77 } 78 } 79 } 80 81 int main() 82 { 83 int n; 84 cnt1=cnt2=0; 85 struct node *head1=null,*head2=null; 86 head1 = arr_mal(head1); 87 head2 = arr_mal(head2); 88 scanf("%d",&n); 89 arr_create(head1,n); 90 arr_split(head1,head2); 91 printf("%d %d\n",cnt2,cnt1); 92 arr_prin(head2); 93 arr_prin(head1); 94 return 0; 95 }