当前位置：首页 > article >正文

2025-03-25 学习记录--C/C++-PTA 习题11-7 奇数值结点链表

article 2025/3/29 17:13:56

合抱之木，生于毫末；九层之台，起于累土；千里之行，始于足下。💪🏻

一、题目描述 ⭐️

习题11-7 奇数值结点链表

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

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

二、代码（C语言）⭐️

// 创建一个新节点
struct ListNode* createNode(int data) {
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode)); // 动态分配内存创建新节点
    newNode -> data = data; // 设置节点的数据域为传入的data
    newNode -> next = NULL; // 设置节点的next指针为NULL
    return newNode; // 返回新创建的节点
}

// 从标准输入读入一系列正整数，按照读入顺序建立单链表
struct ListNode *readlist() {
    int cnt = 0; // 计数器，记录输入的整数个数
    int numArr[1000]; // 数组，用于暂存输入的整数
    do{
        scanf("%d",&numArr[cnt]); // 读取输入的数字
        if(numArr[cnt] == -1) break; // 如果输入-1，结束输入
        cnt++; // 计数器递增
    }while(1); // 无限循环，直到遇到break

    if(cnt == 0) return NULL; // 如果没有输入任何数字（除了-1），返回空链表

    struct ListNode *L = createNode(numArr[0]); // 创建链表的第一个节点
    struct ListNode *p = L; // 指针p指向当前链表的最后一个节点
    for(int i = 1; i < cnt; i++) { // 循环处理剩余的数字
        p -> next = createNode(numArr[i]); // 创建新节点并链接到链表的末尾
        p = p -> next; // 移动指针p到新的末尾节点
    }

    return L; // 返回链表的头指针
}

struct ListNode *getodd( struct ListNode **L ) {
    struct ListNode *oddHead = NULL; // 奇数链表的头指针
    struct ListNode *oddTail = NULL; // 奇数链表的尾指针
    struct ListNode *evenHead = NULL; // 偶数链表的头指针
    struct ListNode *evenTail = NULL; // 偶数链表的尾指针
    struct ListNode *current = *L; // 当前遍历的节点指针

    while(current != NULL) { // 遍历原链表
        if(current -> data % 2 != 0) { // 如果当前节点的数据是奇数
            if(oddHead == NULL) { // 如果奇数链表为空
                oddHead = current; // 设置奇数链表的头指针
                oddTail = current; // 设置奇数链表的尾指针
            } else { // 如果奇数链表不为空
                oddTail -> next = current; // 将当前节点链接到奇数链表的末尾
                oddTail = oddTail -> next; // 移动奇数链表的尾指针
            }
        } else { // 如果当前节点的数据是偶数
            if(evenHead == NULL) { // 如果偶数链表为空
                evenHead = current; // 设置偶数链表的头指针
                evenTail = current; // 设置偶数链表的尾指针
            } else { // 如果偶数链表不为空
                evenTail -> next = current; // 将当前节点链接到偶数链表的末尾
                evenTail = evenTail -> next; // 移动偶数链表的尾指针
            }
        }
        current = current -> next; // 移动到下一个节点
    }

    if (oddTail != NULL) { // 如果奇数链表不为空
        oddTail->next = NULL; // 设置奇数链表的末尾节点的next为NULL
    }
    if (evenTail != NULL) { // 如果偶数链表不为空
        evenTail->next = NULL; // 设置偶数链表的末尾节点的next为NULL
    }
    
    *L = evenHead; // 更新原链表的头指针为偶数链表的头指针
    return oddHead; // 返回奇数链表的头指针
}

代码解释 📚

1、createNode函数：🎀
动态分配内存创建一个新的链表节点。
设置节点的data为传入的参数data。
设置节点的next指针为NULL。
返回新创建的节点。

2、readlist函数：🎀
使用循环读取输入的数字，存储到数组numArr中，直到遇到-1为止。
如果没有输入任何数字（除了-1），返回NULL表示空链表。
创建链表的第一个节点，并使用指针p指向当前链表的最后一个节点。
循环处理剩余的数字，逐个创建新节点并链接到链表的末尾。
返回链表的头指针。

3、getodd函数：🎀
初始化四个指针：oddHead和oddTail用于构建奇数链表，evenHead和evenTail用于构建偶数链表。
遍历原链表，根据节点数据的奇偶性，将节点分别链接到奇数或偶数链表的尾部。
遍历结束后，将奇数链表和偶数链表的尾节点的next置为NULL，确保链表正确终止。
更新原链表头指针*L指向偶数链表的头节点，返回奇数链表的头节点。