学步园

题目来自：http://fayaa.com/tiku/view/6/

1.问题：

设计一个算法，找出一个无环的单链表里面倒数第k个元素，速度要快！

2.思路：

找中间那个，可以用二个指针同时遍历，一个步进2，一个步进1，当前面的到达末尾的时候，后面正好指向中间。 找第K个的话，也是用二个first,second. first先走，当走到第(k-1)个时候，second开始走，当first大道链表末尾的时候，second即为倒数第k个元素。

3.代码实例：

#include<iostream>
#include<stdlib.h>
using namespace std;

typedef int ElemType;

//链表结点结构体
typedef struct Node
{
	ElemType data;		//链表结点中的数据域
	struct Node *next;  //链表结点中的指针域
}Node,*LinkList;


void LinkListCreateHead(LinkList &L,int n)//创建指定长度的单链表，使用头插法,逆序插入
{
	L=(LinkList)malloc(sizeof(Node));
	L->next=NULL;
	LinkList p;
	for(int i=0;i<n;i++)//在头结点L后面插入新的结点p
	{
		p=(LinkList)malloc(sizeof(Node));
		cin>>p->data;
		p->next=L->next;
		L->next=p;//L一直都是头结点
	}
}

void LinkListCreateTail(LinkList &L,int n)//创建指定长度的单链表，使用尾插法,顺序插入
{
	L=(LinkList)malloc(sizeof(Node));
	L->next=NULL;
	LinkList p,q;
	q=L;
	for(int i=0;i<n;i++)//在单链表最后插入结点
	{
		p=(LinkList)malloc(sizeof(Node));
		cin>>p->data;
		q->next=p;
		q=p;
	}
	p->next=NULL;//最后p指向NULL
}

/*
//已经排好序的两个链表合并
void Merge(LinkList &LM,LinkList LH,LinkList LT)//使用尾插法。
{
	//cout<<"111"<<endl;
	LM=(LinkList)malloc(sizeof(Node));//建立合并单链表
	LM->next=NULL;
	LinkList pm,ph,pt;
	ph=LH->next;
	pt=LT->next;
	pm=LM;

	while(ph&&pt)//当pt或者pt有一个到达链表末尾，就可以停止while循环
	{
		if(ph->data<pt->data)
		{
			pm->next=ph;
			pm=ph;
			ph=ph->next;
		}
		else
		{
			pm->next=pt;
			pm=pt;
			pt=pt->next;
		}
	}
	pm->next=ph?ph:pt;//如果最后ph不为空则pm->next指向ph,否则指向pt
}
*/
/*1 2 3 4 5 6 7 8 9 10*/

int FindElem(LinkList L,int k)
{
	LinkList first,second;
	first=L;
	second=L;
	
	int count=0;
	while(count<k-1)
	{
		first=first->next;
		//cout<<first->data<<endl;
		count++;
	}
	while(first->next!=NULL)
	{
		first=first->next;
		second=second->next;
		//cout<<second->data;
	}
	cout<<"first->data:"<<first->data<<endl;
	return second->data;
	//return 0;
}

int main()
{
	LinkList LH,LT,LM;
	int n;
	cout<<"输入链表长度："<<endl;
	cin>>n;

	/*
	cout<<"构建LinkListCreateHead(LH,n)"<<endl;
	LinkListCreateHead(LH,n);
	while(LH->next!=NULL)
	{
		//注意点，输出的是：LH->next->data，而不是LH->data，头结点没有数据
		cout<<LH->next->data<<" ";
		LH=LH->next;
	}
	cout<<endl;
	*/

	cout<<"构建LinkListCreateTail(LT,n)"<<endl;
	LinkListCreateTail(LT,n);
	/*
	while(LT->next!=NULL)
	{
		//注意点，输出的是：LT->next->data，而不是LT->data，头结点没有数据
		cout<<LT->next->data<<" ";
		LT=LT->next;
	}
	cout<<endl;
	*/

	int k=4;
	int e=FindElem(LT,k);
	cout<<"倒数第"<<k<<"个元素："<<e<<endl;

	system("pause");
	return 0;
}


/*
输入链表长度：
5
构建LinkListCreateHead(LH,n)：逆序输出
1 2 3 4 5
5 4 3 2 1
构建LinkListCreateTail(LT,n)：顺序输出
1 2 3 4 5
1 2 3 4 5
请按任意键继续. . .
*/

/*
输入链表长度：
10
构建LinkListCreateTail(LT,n)
1 2 3 4 5 6 7 8 9 10
first->data:10
倒数第4个元素：7
请按任意键继续. . .
*/

second-first=k-1，即first和second指针所指向的元素位置应该相差k-1个。