奇数值结点链表 (20 分)

本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中奇数值的结点重新组成一个新的链表。链表结点定义如下：

 struct ListNode {
    int data;
    ListNode *next;
    };

函数接口定义：

struct ListNode *readlist();
struct ListNode *getodd( struct ListNode **L );

函数readlist从标准输入读入一系列正整数，按照读入顺序建立单链表。当读到−1时表示输入结束，函数应返回指向单链表头结点的指针。

函数getodd将单链表L中奇数值的结点分离出来，重新组成一个新的链表。返回指向新链表头结点的指针，同时将L中存储的地址改为删除了奇数值结点后的链表的头结点地址（所以要传入L的指针）。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *readlist();
struct ListNode *getodd( struct ListNode **L );
void printlist( struct ListNode *L )
{
     struct ListNode *p = L;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode *L, *Odd;
    L = readlist();
    Odd = getodd(&L);
    printlist(Odd);
    printlist(L);

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

1 2 2 3 4 5 6 7 -1

输出样例：

1 3 5 7 
2 2 4 6 

code

struct ListNode *readlist()
{
    typedef struct ListNode *list;
    list head,p,t;//head为头结点,p为结点，t为临时结点
    head=(list)malloc(sizeof(struct ListNode));
    head->next=NULL; //头结点指针域为空，空链表，且头结点数据域未存储信息，数据从下一个结点开始存储
    t=head;

    while(1)
    {
        p=(list)malloc(sizeof(struct ListNode));
        scanf("%d",&p->data);
        if(p->data==-1)
        {
            break;
        }
        p->next=NULL;
        t->next=p;
        t=p;
    }
    return head;
}

/*函数getodd将单链表L中奇数值的结点分离出来，重新组成一个新的链表。 返回指向新链表头结点的指针，同时将L中存储的地址改为删除了奇数值结点后的链表的头结点地址*/
struct ListNode *getodd( struct ListNode **L )
{
    typedef struct ListNode *list;
    list p,t2;  //P为新链表的结点，t2为临时结点
    list head,t1,q;  //head为新链表的头指针，q为新链表的结点，t1为临时结点
    p=(*L)->next; //P指向头结点的下一个
    t2=*L;  //t2初始化为p的上一个结点，下面的delete结点的操作会使用到
    /*奇数值结点的新链表头指针新建*/
    head=(list)malloc(sizeof(struct ListNode));
    head->next=NULL;
    t1=head;

    //遍历单链表
    while(p)
    {
        if(p->data%2)
        {
            /*创建奇数值结点的新链表*/
            q=(list)malloc(sizeof(struct ListNode));
            q->data=p->data;
            t1->next=q;
            q->next=NULL;
            t1=q;

            /*从旧的链表中删除奇数值结点*/
            t2->next=p->next;
            free(p);
            p=t2;
        }
        t2=p; //t2始终为p的上一个结点
        p=p->next;
    }
    *L=(*L)->next; //头结点未存储数据，指向下一个结点，配合输出函数进行输出
    return head->next;
}