PTA（链表）2-10 在单链表 list 的第 i 个位置上插入元素 x

2-10 在单链表 list 的第 i 个位置上插入元素 x

分数 3

作者 陈越

单位 浙江大学

请编写程序，将 n 个整数插入初始为空的单链表，第 i 个整数插入在第 i 个位置上。注意：i 代表位序，从 1 开始。插入结束后，输出链表长度，并顺序输出链表中的每个结点的数值。最后，尝试将最后一个整数插入到链表的第 0 个、第 n+2 个位置上，以测试错误信息的输出。

输入格式：

输入首先在第一行给出正整数 n（≤20）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔。

输出格式：

按照题面描述的要求，首先在第 1 行输出链表信息，格式为：

表长: x1 x2 ... xn

注意数字间有 1 个空格分隔，行首尾无多余空格。
在第 2、3 行分别输出将最后一个整数插入到链表的第 0 个、第 n+2 个位置上的信息 —— 当插入位置不合法时，应输出 错误：插入位置不合法。。

输入样例：

5
1 2 3 4 5

输出样例：

5: 1 2 3 4 5
错误：插入位置不合法。
错误：插入位置不合法。

依旧是之前写过的题目，我再敲一遍

答案

#include <iostream>
using namespace std;

// 定义链表结构
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化链表
void initList(LinkList &L) {
    L = new LNode;
    L->next = NULL;
}

// 尾插法插入链表
void insertAtTail(LinkList &tail, int num) {
    LinkList newNode = new LNode;
    newNode->data = num;
    newNode->next = NULL;
    tail->next = newNode;
    tail = newNode; // 更新尾指针
}

// 将插入到第x位置
bool insertElem(LinkList &L, int x, int num, int n) {
    if (x < 1 || x > n+1) { // 插入位置不合法
        return false;
    }
    // 找到第x-1个位置，便于插入链表
    LinkList p = L->next; // 定义指针p便于遍历
    for (int i = 0; i < x-1; i++) {
        p = p->next;
    }
    // 插入（虽然此题没要求插入到其他位置上）
    LinkList newNode = new LNode;
    newNode->data = num;
    newNode->next = p->next;
    p->next = newNode;
    return true;
}

// 输出表的信息
void printList(LinkList L, int n) {
    cout << n << ":";
    // 定义一个指针便于遍历
    LinkList p = L->next;
    while (p != NULL) {
        cout << " " << p->data;
        p = p->next;
    }
    cout << endl;
}

int main() {
    LinkList L;
    initList(L);
    int n, num;
    cin >> n;

    // 定义尾指针tail，便于插入
    LinkList tail = L;
    for (int i = 0; i < n; ++i) {
        cin >> num;
        insertAtTail(tail, num);
    }
    // 输出表信息
    printList(L, n);
    bool isInsert1, isInsert2;
    isInsert1 = insertElem(L, 0, num, n); // 将num插入到表长为n的链表L的0位置
    if (!isInsert1) {
        cout << "错误：插入位置不合法。" << endl;
    }
    isInsert2 = insertElem(L, n+2, num, n); // 将num插入到表长为n的链表L的n+2上
    if (!isInsert2) {
        cout << "错误：插入位置不合法。";
    }
}