求链表中倒数第K个节点

求链表中倒数第K个节点，思路很简单我们在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前，第二个指针保持不动；在第k-1步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。

实现代码如下：

基本思路:

(1)将pSlow和pFast同时指向链表的头部

（2）将快指针向后移动K位

（3）快慢指针同时移动，当pFast为空时，pSlow就指向倒数第K个节点

（4）结束

算法：

// FindDaoShuK.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

typedef struct node
{
int data;
struct node* next;
}Node;

Node* create_Link(int num)
{
Node* head,*p,*q;
p=new Node();
p->data=1;
head=p;
for (int i=2;i<=num;i++)
{
q=new Node();
q->data=i;
p->next=q;
p=q;
}
p=NULL;//最后一个节点指向空
return head;
}

Node* FindK(Node* head,int k)
{
Node* pslow,*pfast;
pslow=pfast=head;
int i=0;
while(i<k)
{
pfast=pfast->next;
i++;
}
while(pfast)
{
pfast=pfast->next;
pslow=pslow->next;
}
return pslow;
}

int _tmain(int argc, _TCHAR* argv[])
{
Node* head = create_Link(10);
Node* kNode=FindK(head,2);
cout<<kNode->data<<endl;

system("pause");
return 0;
}

基本思路:

(1)将pSlow和pFast同时指向链表的头部

（2）将快指针向后移动K位

（3）快慢指针同时移动，当pFast为空时，pSlow就指向倒数第K个节点

（4）结束

算法：




// FindDaoShuK.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;


typedef struct node
{
	int data;
	struct node* next;
}Node;

Node* create_Link(int num)
{
	Node* head,*p,*q;
	p=new Node();
	p->data=1;
	head=p;
	for (int i=2;i<=num;i++)
	{
		q=new Node();
		q->data=i;
		p->next=q;
		p=q;
	}
	p=NULL;//最后一个节点指向空
	return head;
}

Node* FindK(Node* head,int k)
{
	Node* pslow,*pfast;
	pslow=pfast=head;
	int i=0;
	while(i<k)
	{
		pfast=pfast->next;
		i++;
	}
	while(pfast)
	{
		pfast=pfast->next;
		pslow=pslow->next;
	}
	return pslow;
}



int _tmain(int argc, _TCHAR* argv[])
{
	Node* head = create_Link(10);
	Node* kNode=FindK(head,2);
	cout<<kNode->data<<endl;

	system("pause");
	return 0;
}