習(xí)題11-7 奇數(shù)值結(jié)點(diǎn)鏈表 (20 分)

1. 題目摘自

https://pintia.cn/problem-sets/12/problems/365

2. 題目?jī)?nèi)容

本題要求實(shí)現(xiàn)兩個(gè)函數(shù)溺拱，分別將讀入的數(shù)據(jù)存儲(chǔ)為單鏈表叫惊、將鏈表中奇數(shù)值的結(jié)點(diǎn)重新組成一個(gè)新的鏈表妥粟。鏈表結(jié)點(diǎn)定義如下：

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

函數(shù)接口定義：

struct ListNode *readlist();
struct ListNode *getodd( struct ListNode **L );
函數(shù)readlist從標(biāo)準(zhǔn)輸入讀入一系列正整數(shù)，按照讀入順序建立單鏈表嵌屎。當(dāng)讀到?1時(shí)表示輸入結(jié)束，函數(shù)應(yīng)返回指向單鏈表頭結(jié)點(diǎn)的指針恍涂。

函數(shù)getodd將單鏈表L中奇數(shù)值的結(jié)點(diǎn)分離出來宝惰，重新組成一個(gè)新的鏈表。返回指向新鏈表頭結(jié)點(diǎn)的指針再沧，同時(shí)將L中存儲(chǔ)的地址改為刪除了奇數(shù)值結(jié)點(diǎn)后的鏈表的頭結(jié)點(diǎn)地址（所以要傳入L的指針）尼夺。

輸入樣例：

1 2 2 3 4 5 6 7 -1

輸出樣例：

1 3 5 7
2 2 4 6

3. 源碼參考

#include <iostream>
#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;
}

struct ListNode *readlist()
{
    int n;
    struct ListNode *h, *t, *p;

    h = t = NULL;
    scanf("%d", &n);

    while (n != -1)
    {
        p = (struct ListNode*)malloc(sizeof(struct ListNode));

        p->data = n;
        p->next = NULL;

        if (h == NULL)
        {
            h = p;
        }
        else
        {
            t->next = p;
        }

        t = p;
        scanf("%d", &n);
    }

    return h;
}

struct ListNode *getodd(struct ListNode **L)
{
    struct ListNode *h, *t, *p;
    int a[100], b[100], c[100];
    int i, n;
    int bi, ci;

    n = 0;
    p = *L;

    while (p)
    {
        a[n++] = p->data;
        p = p->next;
    }

    bi = ci = 0;

    for (i = 0; i < n; i++)
    {
        if (a[i] % 2 == 0)
        {
            b[bi++] = a[i];
        }
        else
        {
            c[ci++] = a[i];
        }
    }

    h = t = NULL;

    for (i = 0; i < bi; i++)
    {
        p = (struct ListNode*)malloc(sizeof(struct ListNode));

        p->data = b[i];
        p->next = NULL;

        if (h == NULL)
        {
            h = p;
        }
        else
        {
            t->next = p;
        }

        t = p;
    }

    *L = h;
    h = t = NULL;

    for (i = 0; i < ci; i++)
    {
        p = (struct ListNode*)malloc(sizeof(struct ListNode));

        p->data = c[i];
        p->next = NULL;

        if (h == NULL)
        {
            h = p;
        }
        else
        {
            t->next = p;
        }

        t = p;
    }

    return h;
}