用一个尽可能高效的算法,查找单向链表(有头结点)中倒数第k个位置上的结点

思路

  定义两个指向链表首结点的指针变量,第一个指针变量向后移动k个位置后,第二个指针变量也开始跟着一起向后移动,直到第一个指针变量指向尾结点为止,第二个指针变量指向的位置结点就是倒数第k个结点。

实现步骤及参考代码(C语言)

int LList_FindLK(LList_t *Head, DataType_t data, int k){
	// 1.定义两个指向首结点的指针变量
	LList_t *Temp1 = Head->next;
	LList_t *Temp2 = Head->next;
	
	// 2.定义一个计数器,判定什么时候到第k个位置
	int count = 0;
	
	// 3.Temp1从首结点开始遍历
	while(Temp1->next != NULL)
	{
		Temp1 = Temp1->next;
		
		// 4.每移动一次,计数器+1
		count++;
		
		// 5.如果计数器的值小于k,说明没有找到第k个位置,返回0
		if(count < k)
		{
			return 0;
		}
		// 6.如果计数器的值大于等于k,Temp2开始跟着Temp1移动
		else
		{
			Temp2 = Temp2->next;
		}
	}
	
	// 7.说明Temp1已经指向尾结点,此时Temp2指向的位置即为倒数第k个结点,输出Temp2的data值并返回1
	printf("单向链表中倒数第k个位置结点的data值为:%d",Temp2->data);
	return 1;
}

热门相关:强宠头号鲜妻:陆少,滚!   亿万老公,送上门!   邪王追妻99次:娘子,等我   涅墨西斯黄金螺旋之谜   我的女友不可能是怪物