愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

PAT-练习3:链表操作

定义一个单向链表,并有基本运算:

Node* creatNode()用于创建链表;
void print(struct Node head)用于输出链表;
Node
deleteNode(struct Node *head) 用于删除链表中偶数值结点。
编程实现:输入一个 T 表示有T组case,对于每个case,输入若干个正整数(输入-1为结束标志),建立一个单向链表,将其中的偶数值结点删除后输出。 链表节点定义为:
struct Node{
int data;
struct Node *next;
};
输入输出示例:

输入:
1
1 2 3 4 5 6 7 -1
输出:
1 3 5 7
Sample Input:
1
10 9 8 7 6 5 4 3 2 1 0 -1
Sample Output:
9 7 5 3 1

#include <iostream>
using namespace std;
struct Node{
    int data;
    Node * next;
};

Node * creatNode() {
    Node * head = NULL, *p1 = NULL, *p2 = NULL;
    p1 = new Node;
    cin >> p1->data;
    while (p1->data != -1) {
        if(head == NULL) head = p1;
        else p2->next = p1;
        p2 = p1;
        p1 = new Node;
        cin >> p1->data;
    }
    if(head!=NULL) p2->next = NULL;
    return head;
}

Node * deleteNode(Node *head) {
    Node *p=head, *pre=NULL;
    if(head!=NULL) {
        do {
            if(p->data%2==0) {
                if(pre==NULL) {
                    head=p->next;
                    pre = NULL;
                    p = p->next;
                } else {
                    pre->next = p->next;
                    p = p->next;
                }
            } else {
                pre = p;
                p = p->next;
            }
        } while(p!=NULL);
    }
    return head;
}

void print(Node *head) {
    Node * p = head;
    do {
        cout << p->data;
        if(p->next != NULL) cout << " ";
        p = p->next;
    } while(p!=NULL);
    cout << endl;
}

int main() {
    int T;
    cin >> T;
    while(T>0) {
        Node * p = creatNode();
        print(deleteNode(p));
        T--;
    }
    
    return 0;
}