数据结构/PTA-求链式线性表的倒数第K项/链表

求链式线性表的倒数第K项 

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。

输入格式:

输入首先给出一个正整数K，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。

输出格式:

输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息NULL。

输入样例:

4 1 2 3 4 5 6 7 8 9 0 -1

输出样例:

7

 思路：该题题面很好理解，第一考虑是使用数组做，但出现了多个 段错误 测试点

段错误

• 这个错误一般在程序使用数组这种结构才会出现错误，如果定义数组长度太小，没有达到题目要求最大值的情况。
  比如这个题目：
  
  这里有提到字符串长度不超过10000，这个时候你定义数组就要超过这个值，否则引起段错误或答案错误。比如你可以定义char str[10010];

• scanf没有加&

• 野指针。指针没有指向。如

           int *p; 
           printf("%d", *p1);

           主要的错误原因是数组无论怎么设长度都判断为太小

           然后考虑常规的链表做法

代码：

#include<bits/stdc++.h>
using namespace std;
typedef struct Node
   {
     int data;
     Node *next;
   } Node,*List;
void CreatList(List &s)            //创建链表（输入数值）
   {
     Node *p,*q;
     s=(Node*)malloc(sizeof(Node));
     q=s;
     int x;

     while(scanf("%d",&x)&&x>=0)
      {
        p = (Node *)malloc(sizeof(Node));  // 生成新结点
        p->data = x;
        p->next = s->next; // 插入到表头
        s->next = p;
       }
   }
int main()
   {
     int k;
     scanf("%d",&k);
     List L;
     CreatList(L);
     for(int i = 0;i<k;i++)      //开始读数
     {
       L = L->next;
      }
     if(L->data!=NULL)
            printf("%d",L->data);
    else
            printf("NULL");
     return 0;
   }

 

数据结构/PTA-求链式线性表的倒数第K项/链表

原文：https://www.cnblogs.com/elegantcloud/p/13709077.html