PTA: 奇数值结点链表(C语言版)

水深无声 2023-07-25 14:03 18阅读 0赞

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

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 § \{  
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

struct ListNode *readlist()
    { 
        //因为需要正序输出，故可采用尾插法 
        struct ListNode *head, *p, *q, *tail;
        head = (struct ListNode*)malloc(sizeof(struct ListNode));
        head->next = NULL;
        tail = head;
        while (1)
        { 
            int temp;
            scanf("%d", &temp);
            if (temp == -1)  //当读到-1时退出while循环 
                break;
            p = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->data = temp;
            tail->next = p;
            p->next = NULL;
            tail = p;
        }
    
        return head->next;   //不能返回head，因为题目printlist函数是直接输出p->data的而head是空结点 
    }
    //为什么用**L二级指针？
    //我们知道传递形参时，无法通过形参改变实参值，我们可以通过指针或者c++中的引用来改变实参值
    //*L，同理可以改变*L所指的值得大小，而没办法改变自身，自身就是L，即地址
    //故我们**L通过二级指针可以改变*L，即地址
    struct ListNode *getodd( struct ListNode **L )
    { 
        struct ListNode *head, *p, *q, *OddHead, *tail;
        int  i, j, a[100];
    
        head = *L;
        i = 0;
        while ((head->data % 2) == 1)    //跳过奇数结点，找到第一个偶数结点
        { 
            a[i++] = head->data; //储存奇数结点的data大小
            head = head->next;
            if (head == NULL)
                break;
        }
        p = head;
        while (p != NULL)
        { 
            //删除奇数结点
            if ((p->data % 2) != 0)
            { 
                a[i++] = p->data;
                q->next = p->next;
                p = p->next;
                continue;
            }
            q = p;
            p = p->next;
        }
        *L = head;  //偶数链表头节点
        //构造奇数链表
        OddHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        tail = OddHead;
        for (j = 0; j < i; j++)
        { 
           p = (struct ListNode*)malloc(sizeof(struct ListNode));
           p->data = a[j];
           p->next = NULL;
           tail->next = p;
           tail = p;
        }
    
        return OddHead->next;
    }