查找单链表中倒数第k个节点的最优算法

优雅的算法 TOMORROW 3个月前 (09-05) 318次浏览 0个评论 扫描二维码
文章目录[隐藏]

假设单链表只给出头指针,长度为 n,在不改变链表的前提下,查找链表中倒数第 k 个位置上的结点。要求设计尽可能高效的算法(最优算法),并分析时间复杂度和空间复杂度。

最优算法的基本设计思想

  • 定义两个指针变量 p 和 q,初始时均指向第一个结点;
  • 然后 p 随着链表移动;
  • 当 p 指针移动到第 k 个结点时,q 指针开始与 p 指针同步移动,也就是 p 移动一个结点,q 也移动一个结点;
  • 直到 p 移动到最后一个结点,此时 q 也就是移动到了链表的倒数第 k 个结点。

查找单链表中倒数第 k 个节点的最优算法

最优查找算法的 C 语言源码实现

以上算法的 C 语言源码实现

/*查找单链表倒数第 k 个节点*/

typedef struct LNode
{
	int data;
	struct LNode *link;
}LNode,*LinkList;

int search_k(LinkList list, int k)
{
	LNode *p=list->link,*q=list->link;
	int count=0;
	while(p!=NULL)
	{
		if(count<k)
			count++;
		else
			q=q->link;

		p=p->link;
	}

	if(count<k)/*链表元素少于 k,查找失败*/
		return 0;
	else/*查找成功,输出结果*/
	{
		printf("%d",q->data);
		return 1;
	}	

}

复杂度分析

显而易见的空间复杂度为 O(1);

时间复杂度为 O(n)。

 

 


TOMORROW 星辰 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:查找单链表中倒数第 k 个节点的最优算法
喜欢 (0)
TOMORROW
关于作者:
TOMORROW星辰第一作者。如有疑问或者发现错误,请留言作者。
舒服的野狼发表我的评论  如需接收评论回复通知,请填写正确的 个人信息
取消评论
表情 加粗 斜体 签到