数据结构(C语言版) 线性表 算法设计Demo13

设计一个最优的算法实现输出链表中倒数第k个结点，定义链表结构如下：

Struct ListNode{
	int value;
	ListNode * next;
}

[算法分析]

最直接的想法是首先遍历一次链表得到链表的长度n，倒数第k个结点就是整数n-k+1个结点，然后再遍历链表到第n-k+1个结点即可。想法没有问题，只是不符合题目的“最优”要求，“最优”是要求时间、空间复杂度最小。最佳的方案是只遍历一次链表。思路是声明两个指针p1和p2，首先让p1移动k-1步，然后p1、p2同时移动，直到p1->next为空，p2所指向的结点就是倒数第k个结点。

[算法描述]

ListNode * FindKthToTail(List * head,int k){
	ListNode * p1,p2=head;
	for(int i=0;i
		p1=p1->next;
	}
	while(p1->next){
		p1=p1->next;
		p2=p2->next;
	}
	return p2;
}