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

优雅的算法 TOMORROW 1年前 (2018-09-05) 1530次浏览 2个评论 扫描二维码
文章目录[隐藏]

假设单链表只给出头指针,长度为 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 个节点的最优算法
喜欢 (1)
TOMORROW
关于作者:
一个从石头坑掉到泥坑里的攻城狮。
缓慢的奇异果发表我的评论  请填写正确的 个人信息
取消评论
表情 加粗 斜体 签到
(2)个小伙伴在吐槽
  1. Indian Viagra Tablets Beipackzettel Viagra Online buy viagra online Buy Cheap Bupropion 150mg In Usa Buy. Amytryptline
    Franfom2019-06-02 03:49 回复 Windows 8 | Chrome 68.0.3440.106
  2. 哇塞,居然是沙发?留个名
    fde22i42019-05-05 21:08 回复 Windows 7 | 未知浏览器