查找链表中倒数第k个结点（C++）

描述

利用单链表表示一个整数序列，请实现一个时间复杂度为O(n)、空间复杂度为O(1)的算法，通过一趟遍历在单链表中确定倒数第k个结点。

输入

多组数据，每组数据有三行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔），第三行为k。当n=0时输入结束。

输出

对于每组数据分别输出一行，输出每个链表的倒数第k个结点对应的数值。

输入样例 1

7
5 2 3 4 50 100 70
3
5
20 30 10 4 5
5
0

输出样例 1

50
20

思路：

说是倒数第k个节点，但是我们可以稍微转化一下把倒数转成正数来处理，这样就不用倒序了~在遍历的时候，由于题目给的是“第k个”节点，是节点的位置信息，而不是节点的数据信息，所以这种情况下采用for循环为主，p节点（为了取出数据）为辅的方式是妥当的。

同时，一旦找到，break就可以了，这样就更快了~

#include
#include
#include
#include
#include
#include
using namespace std;
typedef struct LNode
{
	int data;
	LNode* next;
}*linklist, LNode;
void TailInsert(linklist& l, int n)
{
	l = new LNode;
	l->next = NULL;
	linklist rear = l;
	for (int i = 0; i < n; i++)
	{
		linklist p = new LNode;
		cin >> p->data;
		rear->next = p;
		rear = p;
	}
	rear->next = NULL;//不可或缺
}
void Find(linklist l, int n,int pos)
{
	linklist p = l->next;
	for (int i = 1; i <= n; i++)
	{
		if (i == n-pos+1)
		{
			cout << p->data << endl;
			break;
		}
		p = p->next;
	}
}
int main()
{
	int n;
	cin >> n;
	while (n)
	{
		linklist l;
		TailInsert(l,n);
		int pos;
		cin >> pos;
		Find(l, n, pos);
		cin >> n;
	}
	return 0;
}

查找链表中倒数第k个结点（C++）

C/C++/C#相关栏目本月热门文章