学步园

题目：输入一个单向链表，输出该链表中倒数第k个结点。链表结点定义如下：

struct node
{
int value;
node *m_next;
};

思想：两个指针，开始时同时指向头节点，然后一个指针向后移K位后，两个指针同时向后移，知道后面一个指针为尾指针是停止，这时第一个指针指的位置即为倒数第k个节点。

//输出链表的倒数第K个节点
#include <iostream>
using namespace std;
struct node
{
	int value;
	node *m_next;
};
void makenode(node *&ptr, int value)
{
	if (ptr==nullptr)
	{
		node *current=new node();
		current->value=value;
		current->m_next=nullptr;
		ptr=current;
	}
	else
	{
		makenode(ptr->m_next,value);
	}
}
void Findkthnode(node *ptr,int k)
{
	if (ptr==nullptr)
	{
		return;
	}
	node *beg=ptr;
	node *end=ptr;
	for (int i=1;i<k;++i)
	{
		if (end->m_next!=nullptr)
		{
			end=end->m_next;
		}
		else
		{
			return;
		}
	}
	while (end->m_next!=nullptr)
	{
		end=end->m_next;
		beg=beg->m_next;
	}
	cout<<beg->value<<endl;
}

int main()
{
	node *root = nullptr;
	makenode(root,1);
	makenode(root,2);
	makenode(root,3);
	makenode(root,4);
	makenode(root,5);
	makenode(root,6);
	makenode(root,7);
	makenode(root,8);
	makenode(root,9);
	Findkthnode(root,4);
	return 0;
}