1、计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。
输入描述：
输入一行，代表要计算的字符串，非空，长度小于5000。
输出描述：
输出一个整数，表示输入字符串最后一个单词的长度。并把每个单词输出并存储。
示例：
输入：hello nowcoder
输出：8
/*
知识点1：定义字符数组：
const int num = 5001;
char s[num]; //字符数组最后一个字符是不可见字符’\0’
cin.getline(s,num); //cin.getline(字符数组，字符个数，结束标志),第三个参数省略系统默认’\0’
知识点2：字符串流istringstream和ostringstream
istringstream，由 istream 派生而来，提供读 string 的功能
ostringstream，由 ostream 派生而来，提供写 string 的功能
stringstream，由 iostream 派生而来，提供读写 string 的功能
使用上述类时，要带上头文件：
#include <sstream>
代码实现：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
int getLengthofLastWord(string s)
{
int ridx = s.rfind(' ');
int len = s.size();
int lastlen = len - 1 - ridx;
return lastlen;
}
int main()
{
string s1;
//获取字符串
getline(cin,s1); //因为有空格，所以要用getline()函数
int rst=getLengthofLastWord(s1);
cout << rst << endl;
//存储每个单词
vector<string> res;
string out;
stringstream stream(s1);
while (stream >> out)
{
cout << out << endl;
res.push_back(out);
}
return 0;
}
运行结果：
2、写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）
数据范围： n:[1,1000]
输入描述：
第一行输入一个由字母和数字以及空格组成的字符串，第二行输入一个字符。
输出描述：
输出输入字符串中含有该字符的个数。（不区分大小写字母）
代码实现：
#include <iostream>
using namespace std;
int main()
{
//输入字符数组
const int num = 1001;
char s1[num];
cin.getline(s1,num);
//输入字符
char c1;
cin >> c1;
int cnt = 0;
for (int i = 0; s1[i]!='\0'; i++)
{
if (toupper(s1[i])==toupper(c1))
{
cnt++;
}
}
cout << cnt << endl;
return 0;
}
运行结果：
3、随机生成N个1到500之间的随机数
输入描述：输入随机数个数N，并将这N个随机数输出，每行一个数
输出描述：将随机数从小到大排序后输出，每行一个
代码实现：
#include <iostream>
#include <vector>
#include <algorithm> //使用sort需要引用该头文件
using namespace std;
int Random(int start,int end)
{
int dis = end - start;
return rand() % dis + start;
}
int main()
{
int start = 1, end = 500;
int N;
cin >> N;
vector<int> vec;
int cnt = 0;
for (int i = 0; i < N; i++)
{
cnt++;
int tmp = Random(start,end);
vec.push_back(tmp);
cout << tmp << endl;
}
sort(vec.begin(), vec.end()); //默认升序排列,从小到大排序
//reverse(vec.begin(), vec.end()); //降序排列，从大到小
cout << "输出排序结果：" << endl;
for (int i = 0; i < vec.size(); i++)
{
cout << vec[i] << endl;
}
return 0;
}
结果输出：
4、输入n个整数，找出其中最小的k个整数并按升序输出
数据范围：1≤n≤1000 ，输入的整数满足 1≤val≤10000
输入描述：
第一行输入两个整数n和k
第二行输入一个整数数组
输出描述：
从小到大输出最小的k个整数，用空格分开。
代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> vec;
const int max = 1000;
int data[max] = { 0 };
for (int i = 0; i < n; i++)
{
cin >> data[i];
vec.push_back(data[i]);
}
sort(vec.begin(), vec.end());
for (int i = 0; i < k; i++)
{
cout << vec[i]<<" ";
}
return 0;
}
运行结果：
5、输入整型数组和排序标识，对其元素按照升序或降序进行排序
数据范围： 1≤n≤1000 ，元素大小满足 0≤val≤100000
输入描述：
第一行输入数组元素个数
第二行输入待排序的数组，每个数用空格隔开
第三行输入一个整数0或1。0代表升序排序，1代表降序排序
输出描述：
输出排好序的数字
代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, bl;
cin >> n;
const int N = 1000;
static int aa[N];
vector<int> vec;
if ((n >= 1) && (n <= 1000))
{
for (int i = 0; i < n; i++)
{
cin >> aa[i];
vec.push_back(aa[i]);
}
}
cin >> bl;
if (bl == 0)
{
sort(vec.begin(), vec.end());
}
if (bl == 1)
{
sort(vec.begin(), vec.end());
reverse(vec.begin(),vec.end());
}
int sz = vec.size();
for (int i = 0; i < sz; i++)
{
cout << vec[i] << " ";
}
return 0;
}
运行结果：
6、输入一个字符串，请按长度为8拆分每个输入字符串并进行输出；
长度不是8的整数倍的字符串请在后面补数字0，空字符串不处理。
输入描述：
连续输入字符串(每个字符串长度小于等于100)
输出描述：
依次输出所有分割后的长度为8的新字符串
代码实现：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
string str;
while (cin >> str)
{
int len = str.size();
if (len > 100)
{
cout << "请输入小于100的字符" << endl;
}
else
{
vector<string> vect;
int m = len / 8;
for (int i = 0; i < m; i++)
{
vect.push_back(str.substr(i*8,8));
}
if (len % 8 != 0)
{
int tt = 8 - len % 8;
for (int i = 0; i < tt; i++)
{
str += '0';
}
vect.push_back(str.substr(m * 8));
} //if(len%8)
vector<string>::iterator it;
for (it = vect.begin(); it != vect.end(); ++it)
{
cout << *it << endl;
}
} //else
} //while()
return 0;
}
运行结果：
7、HJ5进制转换
接受一个十六进制的数，输出该数值的十进制表示。
数据范围：保证结果在 1≤n≤pow(2,31)−1
输入描述：
输入一个十六进制的数值字符串。
输出描述：
输出该数值的十进制字符串。不同组的测试用例用\n隔开。
代码实现：
#include <iostream>
using namespace std;
int main()
{
int a;
while (cin >> hex >> a) {
cout << a << endl;
}
}
运行结果：
8、HJ6质数因子
功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）
数据范围： 1≤n≤2×pow(10,9) +14
输入描述：
输入一个整数
输出描述：
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。
代码实现：
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int n;
cin >> n;
for (int i = 2; pow(i, 2) <= n; i++)
{
if (n % i == 0)
{
cout << i << " ";
n /= i;
i--;
}
}
cout << n;
return 0;
}
运行结果：
9、HJ8合并记录表
数据表记录包含表索引index和数值value（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照index值升序进行输出。
提示:
0 <= index <= 11111111
1 <= value <= 100000
输入描述：
先输入键值对的个数n（1 <= n <= 500）
接下来n行每行输入成对的index和value值，以空格隔开
输出描述：
输出合并后的键值对（多行）
代码实现：
主要用到STL标准库中的map关联容器，它提供一对一的Hash。
1）第一个为关键字key，每个关键字只能在map中出现一次。
2）第二个称为该关键字的值。
map以模板(泛型)的方式实现，可以存储任意类型的数据，定义及使用方法如下代码所示:
#include <iostream>
#include <map> //STL头文件没有扩展名.h
using namespace std;
int main()
{
int num,key,value;
map<int, int> mp;
cin >> num;
while (num)
{
cin >> key >> value;
//count()方法返回值是一个整数，1表示有这个元素，0表示没有这个元素，以此来判断键值元素是否存在
if (mp.count(key))
{
mp[key] += value;
}
else
{
mp.insert(pair<int, int>(key, value)); //插入元素
}
num--;
}
map<int, int>::iterator it; //迭代器
for (it = mp.begin(); it != mp.end(); it++)
{
cout << it->first << " " << it->second << endl;
}
return 0;
}
运行结果：
10、HJ3明明的随机数
明明生成了N个1到500之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。
数据范围：1≤n≤1000，输入的数字大小满足 1≤val≤500
输入描述：
第一行先输入随机整数的个数 N 。 接下来的 N 行每行输入一个整数，代表明明生成的随机数。
输出描述：
输出多行，表示输入数据处理后的结果
代码实现：
#include <iostream>
#include <vector>
#include <algorithm> //使用sort需要引用该头文件
using namespace std;
int main()
{
int num;
cin >> num;
vector<int> vec(num); //num表示
for (int i = 0; i < num; i++)
{
cin >> vec[i];
}
sort(vec.begin(), vec.end());
/*unique只移除相邻元素，如果要移除所有重复元素，则需要先将数据进行排序，使重复元素相邻
unique()会返回一个迭代器*/
vector<int>::iterator it= unique(vec.begin(), vec.end());
vec.erase(it,vec.end());
//排序后输出
int len = vec.size();
for (int i = 0; i < len; i++)
{
cout << vec[i] << endl;
}
return 0;
}
运行结果如下：
11、HJ10字符个数统计
编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。
数据范围： 1≤n≤500
输入描述：
输入一行没有空格的字符串。
输出描述：
输出 输入字符串中范围在(0~127，包括0和127)字符的种数。
代码实现：
#include <iostream>
#include <vector>
#include <algorithm> //find()函数位于该头文件内
using namespace std;
int charNum(string str)
{
int cnt = 0;
int len = str.length();
vector<char> vec;
for (int i = 0; i < len; i++)
{
if (find(vec.begin(), vec.end(), str[i]) == vec.end())
{
vec.push_back(str[i]);
}
}
cnt = vec.size();
return cnt;
}
int main()
{
string str;
cin >> str;
int num=charNum(str);
cout << num << endl;
return 0;
}
运行结果：
12、HJ11 数字颠倒
描述
输入一个整数，将这个整数以字符串的形式逆序输出
程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001
数据范围： 0≤n≤pow(2,30)−1
输入描述：
输入一个int整数
输出描述：
将这个整数以字符串的形式逆序输出
代码实现：
#include <iostream>
#include <sstream>
using namespace std;
int main()
{
int num;
cin >> num;
stringstream ss;
string res;
while (num / 10 != 0)
{
ss << num % 10;
num /= 10;
}
ss << num % 10; //向流中写入数据
ss >> res; //读出流中的数据
cout << res << endl;
return 0;
}
运行结果：
13、HJ12字符串反转
描述
接受一个只包含小写字母的字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）
输入描述：
输入一行，为一个只包含小写字母的字符串。
输出描述：
输出该字符串反转后的字符串。
代码实现：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
getline(cin, str);
//字符反转
reverse(str.begin(), str.end()); //位于头文件#include<algorithm>
cout << str << endl;
return 0;
}
运行结果：
14、HJ13句子逆序
描述
将一个英文语句以单词为单位逆序排放。例如“I am a boy”，逆序排放后为“boy a am I”
所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符
数据范围：输入的字符串长度满足 1 \le n \le 1000 \1≤n≤1000
注意本题有多组输入
输入描述：
输入一个英文语句，每个单词用空格隔开。保证输入只包含空格和字母。
输出描述：
得到逆序的句子
代码实现：
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
string str;
getline(cin, str);
stringstream stream(str);
string out;
vector<string> vec;
while (stream >> out)
{
vec.push_back(out);
}
reverse(vec.begin(),vec.end());
int len = vec.size();
for (int i = 0; i < len; i++)
{
cout << vec[i] << " ";
}
return 0;
}
运行结果：
15、HJ14字符串排序
描述
给定 n 个字符串，请对 n 个字符串按照字典序排列。
数据范围： 1≤n≤1000 ，字符串长度满足 1≤len≤100
输入描述：
输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。
输出描述：
数据输出n行，输出结果为按照字典序排列的字符串。
代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int N;
cin >> N;
vector<string> vec;
const int max = 1000;
static string data[max];
for (int i = 0; i < N; i++)
{
cin >> data[i];
vec.push_back(data[i]);
}
sort(vec.begin(), vec.end());
int len = vec.size();
for (int i = 0; i < len; i++)
{
cout << vec[i] << endl;
}
return 0;
}
运行结果：
16、HJ15 求int型正整数在内存中存储时1的个数
描述
输入一个 int 型的正整数，计算出该 int 型数据在内存中存储时 1 的个数。
数据范围：保证在 32 位整型数字范围内
输入描述：
输入一个整数（int类型）
输出描述：
这个数转换成2进制后，输出1的个数
代码实现：
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int cnt = 0;
while (n != 0)
{
if (n % 2 != 0) cnt++;
n >>= 1;
}
cout << cnt << endl;
return 0;
}
运行结果：
17、HJ108求最小公倍数
描述
正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。
数据范围：1≤a,b≤100000
输入描述：
输入两个正整数A和B。
输出描述：
输出A和B的最小公倍数。
代码实现：
#include <iostream>
#include <string>
using namespace std;
//计算最大公约数:greatest common divisor
int gcd(int a, int b)
{
int c = 0;
while (c = a % b)
{
a = b;
b = c;
}
return b;
}
//计算最小公倍数：least common multiple
int lcm(int a, int b)
{
int tmp = a * b / gcd(a, b);
return tmp;
}
int main()
{
int a, b;
cin >> a >> b;
int min = lcm(a, b);
cout << min << endl;
return 0;
}
运行结果：
18、HJ106 字符逆序
描述
将一个字符串str的内容颠倒过来，并输出。
数据范围：1≤len(str)≤10000
输入描述：
输入一个字符串，可以有空格
输出描述：
输出逆序的字符串
代码实现：
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str;
getline(cin, str);
int len = str.length();
for (int i = len-1; i >= 0; i--)
{
cout << str[i];
}
return 0;
}
运行结果：
19、HJ102字符统计
描述
输入一个只包含小写英文字母和数字的字符串，按照不同字符统计个数由多到少输出统计结果，如果统计的个数相同，则按照ASCII码由小到大排序输出。
数据范围：字符串长度满足 1≤len(str)≤1000
输入描述：
一个只包含小写英文字母和数字的字符串。
输出描述：
一个字符串，为不同字母出现次数的降序表示。若出现次数相同，则按ASCII码的升序输出。
知识点：
vector初始化方式：
vector<int>vec0; //默认初始化，vec0为空
vector<int>vec1{1,2,3}; //直接赋值
vector<int>vec2(vec1); //用vec1初始化vec2
vector<int>vec3(vec1.begin(), vec1.end()); //用vec1初始化vec3
vector<int>vec4(10); //10个值为0的元素
vector<int>vec5(10,4); //10个值为4的元素
vector<vector<int>>vec6(10, vector<int>(4, 1)); //10*4的二维数组，值全为1
代码实现：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//define struct
struct dat
{
int num;
char ch;
};
//定义排序规则
bool sort1(dat & d1, dat & d2)
{
if (d1.num == d2.num)
{
return d1.ch < d2.ch;
}
else
{
return d1.num > d2.num;
}
}
int main()
{
string str;
getline(cin, str);
//初始化vector，256个值为0的元素,用来保存每个字符的数量
vector<int> char_num(256, 0);
vector<dat> charN;//用来保存对应的某个字符以及数量
//遍历字符串中每个字符出现的次数
int len = str.length();
for (int i = 0; i < len; i++)
{
char_num[str[i]]++;
}
for (int i = 0; i < 256; i++)
{
dat tmp;
tmp.ch = i;
tmp.num = char_num[i];
charN.push_back(tmp);
}
//按照字符数量进行排序，数量相同字典序小的在前
sort(charN.begin(), charN.end(), sort1);
int sz = charN.size();
for (int i = 0; i < sz; i++)
{
if (charN[i].num == 0) break;
cout << charN[i].ch;
}
return 0;
}
运行结果：
20、HJ100等差数列
描述
等差数列 2，5，8，11，14…
（从 2 开始的 3 为公差的等差数列）
输出求等差数列前n项和
数据范围： 1≤n≤1000
输入描述：
输入一个正整数n。
输出描述：
输出一个相加后的整数。
代码实现：
#include <iostream>
using namespace std;
int main()
{
int sum = 0;
int a1 = 2;
int n;
cin >> n;
while (n--)
{
sum += a1;
a1 += 3;
}
cout << sum << endl;
return 0;
}
运行结果：
21、HJ99自守数
描述
自守数是指一个数的平方的尾数等于该数自身的自然数。例如：2525= 625，7676 = 5776，9376*9376 = 87909376。请求出n(包括n)以内的自守数的个数
数据范围： 1≤n≤10000
输入描述：
int型整数
输出描述：
n以内自守数的数量
代码实现：
#include <iostream>
using namespace std;
int main()
{
int base = 10;
int tmp = 1;
int n;
cin >> n;
for (int i = 1;i <= n; i++)
{
int sq = i*i;
if (i == base) base *= 10;
if (sq % base == i) tmp++;
}
cout << tmp << endl;
return 0;
}
运行结果：
22、HJ23 删除字符串中出现次数最少的字符
描述
实现删除字符串中出现次数最少的字符，若出现次数最少的字符有多个，则把出现次数最少的字符都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。
数据范围：输入的字符串长度满足 1≤n≤20 ，保证输入的字符串中仅出现小写字母
输入描述：
字符串只包含小写英文字母, 不考虑非法输入，输入的字符串长度小于等于20个字节。
输出描述：
删除字符串中出现次数最少的字符后的字符串。
代码实现：
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
string s;
const int num = 26;
while (cin >> s)
{
int cnt[num] = { 0 };
//将每个字符出现的次数对应的放在cnt数组中
int len = s.size();
for (int i = 0; i <len ; i++)
{
int tmp = int(s[i] - 'a');
cnt[tmp]++;
}
//找到最小次数的字符并删除
int min = 100;
for (int i = 0; i < num; i++)
{
if ((cnt[i] != 0) && (cnt[i] < min))
{
min = cnt[i];
}
}
//删除最小字符
for (int i = 0; i < num; i++)
{
if (min == cnt[i])
{
s.erase(remove(s.begin(), s.end(), 'a' + i), s.end());
}
}
cout << s << endl;
}
return 0;
}
运行结果：
知识点：vector::remove()函数的使用
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int> vec = {1,1,2,3,4,5,6,7,8,9 };
remove(vec.begin(), vec.end(), 1);
for (int i = 0; i < vec.size(); i++)
{
cout << vec[i] << " ";
}
return 0;
}
运行结果如下：在这里插入图片描述
remove()函数的功能就是将vector中指定的数据移动到vector末尾，注意，上述代码remove将两个1移动到末尾，但是在vector中并不显示出来，也就是说不能输出，但是内存中却存在这个数，需要使用erase才能彻底删除，使用方法如下：
vec.erase(remove(vec.begin(), vec.end(), 1), vec.end());
运行结果如下：
23、HJ31 单词倒排
描述
对字符串中的所有单词进行倒排。
说明：
（1）构成单词的字符只有26个大写或小写英文字母；
（2）非构成单词的字符均视为单词间隔符；
（3）要求倒排后的单词间隔符以一个空格表示；如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；
（4）每个单词最长20个字母；
数据范围：字符串长度满足 1≤n≤10000
输入描述：
输入一行，表示用来倒排的句子
输出描述：
输出句子的倒排结果
代码实现：
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
string str;
while (getline(cin, str))
{
vector<string>svec;
svec.clear();
string temp = "";
for (int i = 0; i < str.size(); ++i)
{
if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && str[i] <= 'Z')
temp += str[i];
else {
if (temp.size() > 0) {
svec.push_back(temp);
temp = "";
}
}
}
if (temp.size() > 0)
svec.push_back(temp);
// 逆序输出
int len = svec.size();
for (int i = len - 1; i >= 0; --i)
cout << svec[i] << ' ';
}
return 0;
}
运行结果如下：
24、HJ97 记负均正
描述
首先输入要输入的整数个数n，然后输入n个整数。输出为n个整数中负数的个数，和所有正整数的平均值，结果保留一位小数。
0即不是正整数，也不是负数，不计入计算。如果没有正数，则平均值为0。
数据范围： 1≤n ≤2000 ，输入的整数都满足 ∣val∣≤1000
输入描述：
首先输入一个正整数n，
然后输入n个整数。
输出描述：
输出负数的个数，和所有正整数的平均值。
代码实现：
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
int N;
cin >> N;
int pos = 0, neg = 0, sum = 0;
for (int i = 0; i < N; i++)
{
int tmp;
cin >> tmp;
if (tmp > 0)
{
pos++;
sum += tmp;
}
else if (tmp < 0)
{
neg++;
}
}
float mean;
if (pos == 0)
{
mean = 0.0;
}
else
{
mean = sum * 1.0 / pos;
}
cout << neg<<" "<< fixed << setprecision(1) << mean << endl;
return 0;
}
运行结果：
25、HJ40 统计字符
描述
输入一行字符，分别统计出包含英文字母、空格、数字和其它字符的个数。
数据范围：输入的字符串长度满足 1≤n≤1000
输入描述：
输入一行字符串，可以有空格
输出描述：
统计其中英文字符，空格字符，数字字符，其他字符的个数
代码实现：
#include<iostream>
#include<string>
using namespace std;
int main()
{
string str;
getline(cin, str);
int cnt_word = 0, cnt_blank = 0, cnt_num = 0, cnt_other = 0;
int sz = str.size();
for (int i = 0; i < sz; i++)
{
if (str[i] >= '0' && str[i] <= '9')
{
cnt_num++;
}
else if ((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'))
{
cnt_word++;
}
else if (str[i] == ' ')
{
cnt_blank++;
}
else
{
cnt_other++;
}
}
cout << cnt_word << endl;
cout << cnt_blank << endl;
cout << cnt_num << endl;
cout << cnt_other << endl;
return 0;
}
运行结果：
26、HJ51 输出单向链表中倒数第k个结点
描述
输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
正常返回倒数第k个结点指针，异常返回空指针.
要求：
(1)正序构建链表;
(2)构建后要忘记链表长度。
数据范围：链表长度满足1≤n≤1000 ，k≤n ，链表中数据满足 0≤val≤10000
本题有多组样例输入。
输入描述：
输入说明
1 输入链表结点个数
2 输入链表的值
3 输入k的值
输出描述：
输出一个整数
代码实现：
#include <iostream>
using namespace std;
//链表节点
struct ListNode
{
int val;
ListNode* next;
//初始化
ListNode(int x):val(x), next(NULL) {}
};
//找到链表倒数第k个节点
ListNode* FindKthToTail(ListNode* pHead, int k) {
int n = 0;
ListNode* fast = pHead;
ListNode* slow = pHead;
//快指针
for (int i = 0; i < k; i++) {
if (fast != NULL)
fast = fast->next;
else
//达不到k,说明链表长度过短，返回空链表
return slow = NULL;
}
//快慢指针同步，快指针先到底，慢指针指向倒数第k个元素
while (fast != NULL)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
int main()
{
int n, val;
//输入n个节点
while (cin >> n) {
cin >> val;
//输入链表第一个节点
ListNode* head = new ListNode(val);
ListNode* p = head;
//输入链表后续节点
for (int i = 1; i < n; i++)
{
cin >> val;
ListNode* q = new ListNode(val);
//连接
p->next = q;
p = p->next;
}
//找到第k个位置
int k;
cin >> k;
//边界条件如果等于0直接返回0
if (k == 0)
cout << 0 << endl;
else {
//找到第k个节点
p = FindKthToTail(head, k);
//只有返回不NULL才输出
if (p != NULL)
cout << p->val << endl;
}
}
return 0;
}
运行结果：