算法2-5 返回单链表 list 中第 i 个元素值

分数 15

作者 陈越

单位 浙江大学

请编写程序，将 n 个整数顺次插入一个初始为空的单链表的表头。对任一给定的位序 i（从 1 开始），输出链表中第 i 个元素的值。

输入格式：

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

输出格式：

在一行中输出链表中第 i 个元素的值。如果这个元素不存在，则输出 -1。

输入样例 1：

5
1 2 3 4 5
4

输出样例 1：

2

输入样例 2：

5
1 2 3 4 5
0

输出样例 2：

-1

解析

#include <iostream>
#include <cstdlib>
using namespace std;
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
int main()
{
    LinkList L;
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        LNode *p = (LNode *)malloc(sizeof(LNode));
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
    int key;
    cin >> key;
    if (key < 1 || key > n)
    {
        cout << "-1" << endl;
        return 0;
    }
    LNode *p = L->next;
    for (int i = 1; i < key; i++)
    {
        p = p->next;
    }
    cout << p->data << endl;
    return 0;
}

注意

1.这个插入顺序是在头节点和第一个节点中间插，以输入样例 1（n=5，整数1 2 3 4 5）为例：

  • 插入1：新节点next=head->next（NULL），head->next=新节点 → 链表：空头→1。
  • 插入2：新节点next=head->next（1），head->next=新节点 → 链表：空头→2→1。
  • 依次插入3、4、5后，最终有效节点顺序：5→4→3→2→1（与输入顺序相反）。