欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【SDUT】【链表】2120 - 数据结构实验之链表五:单链表的拆分

程序员文章站 2022-06-15 17:44:58
Problem Description 输入N个整数顺序建立一个单链表,将该单链表拆分成两个子链表,第一个子链表存放了所有的偶数,第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。 Input 第一行输入整数N;;第二行依次输入N个整数。 Output 第一行分别输出偶数链表与奇 ......

problem description

输入n个整数顺序建立一个单链表,将该单链表拆分成两个子链表,第一个子链表存放了所有的偶数,第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。

input

第一行输入整数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 }