2213: 链表的拆分(线性表)

题目描述

设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一函数，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。

输入

输入长度n：9
输入数据：2 3 5 1 4 17 23 14 19

输出

1 3 5 17 19 23
2 4 14

样例输入

9
12 3 6 7 16 22 27 45 57

样例输出

3 7 27 45 57 
6 12 16 22 

参考代码

#include <stdio.h>
#include <stdlib.h>
typedef struct node 
{
    int data;
    struct node *next;
}
List;
List *Create(int n) 
{
    int i;
    List *head, *p1, *p;
    head = (List *)malloc(sizeof(List));
    head->next = NULL;
    p = head;
    for (i = 0; i < n; i++) 
    {
        p1 = (List *)malloc(sizeof(List));
        scanf("%d", &p1->data);
        p1->next = p->next;
        p->next = p1;
        p = p1;
    }
    return head;
}
void Sort(List *p, int n) 
{
    List *p1, *p2;
    int i, j;
    int tmp;
    p2 = p1 = p;
    for (i = 0; i < n; i++) 
    {
        for (j = 0, p1 = p->next; j < n-i-1; j++) 
        {
            if(p1->data > p1->next->data) 
            {
                tmp = p1->data;
                p1->data = p1->next->data;
                p1->next->data = tmp;
            }
            p1 = p1->next;
        }
    }
}
int main() 
{
    List *head, *p, *p1, *p2, *q1, *q2;
    int n;
    int i, j;
    scanf("%d", &n);
    head = Create(n);
    p = head;
    i = j = 0;
    Sort(p, n);
    while(p->next) 
    {
        p = p->next;
        if(p->data % 2) 
        {
            j++;
            if( j == 1 ) 
            {
                q1 = p1 = p;
            } else 
            {
                p1->next = p;
                p1 = p;
            }
        } else 
        {
            i++;
            if(i == 1) 
            {
                q2 = p2 = p;
            } else 
            {
                p2->next = p;
                p2 = p;
            }
        }
    }
    p2->next = NULL;
    p1->next = NULL;
    while(q1) 
    {
        printf("%d ", q1->data);
        q1 = q1->next;
    }
    printf("n");
    while(q2)
    {
        printf("%d ", q2->data);
        q2 = q2->next;
    }
    printf("n");
    return 0;
}

解析

暂无