热门标签 | HotTags
当前位置:  开发笔记 > 人工智能 > 正文

面试题快慢链表和快慢指针

这篇文章主要介绍了面试题快慢链表和快慢指针的相关资料,需要的朋友可以参考下

腾讯的一道面试题:如何快速找到位置长度单链表的中间节点?普通方法,就是先遍历,在从头找到2/length的中间节点。算法复杂度是:O(3*n/2)。而更快的方法就是利用快慢指针的原理。

快慢链表:利用标尺的思想,设置两个指针(一快一慢)*serach和*mid,刚开始都指向单链表的头结点。但是*search指针的移动速度是*mid的两倍。当*search到尾结点的时候,mid刚好到了中间。算法复杂度是:O(n/2)

int GetMidNode(LinkList *L,int elem){
  LinkList *search,*mid;
  mid = search = L; //指向头结点
  while (search->next != NULL){ //当存在下个结点的时候 
    if (search->next->next!=NULL) {//检查下个的下个节点是否为空 
      search = search->next->next;
      mid = mid->next;
    } 
    else
      search = search->next;
  }
  elem = mid->data;
  return elem;
} 

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!


推荐阅读
  • Excel技巧:单元格中显示公式而非结果的解决方法
    本文探讨了在Excel中如何通过简单的方法解决单元格显示公式而非计算结果的问题,包括使用快捷键和调整单元格格式两种方法。 ... [详细]
  • Java中提取字符串的最后一部分
    本文介绍了如何使用Java中的substring()和split()方法来提取字符串的最后一部分,特别是在处理包含特殊字符的路径时的方法与技巧。 ... [详细]
  • 对于非计算机专业背景的开发者而言,如何快速掌握.NET基础知识以应对技术面试是一个挑战。本文将提供一系列实用建议,帮助读者在短时间内提高.NET基础水平。 ... [详细]
  • 本文介绍了使用Python和C语言编写程序来计算一个给定数值的平方根的方法。通过迭代算法,我们能够精确地得到所需的结果。 ... [详细]
  • 本文提供了一个关于AC自动机(Aho-Corasick Algorithm)的详细解析与实现方法,特别针对P3796题目进行了深入探讨。文章不仅涵盖了AC自动机的基本概念,还重点讲解了如何通过构建失败指针(fail pointer)来提高字符串匹配效率。 ... [详细]
  • 本文提供了一个详尽的前端开发资源列表,涵盖了从基础入门到高级应用的各个方面,包括HTML5、CSS3、JavaScript框架及库、移动开发、API接口、工具与插件等。 ... [详细]
  • 本文介绍了在达梦数据库(DM7)中通过两种方法实现两表之间的联接更新操作,包括使用子查询的更新语句和MERGE语句的具体应用。 ... [详细]
  • SSE图像算法优化系列三:超高速导向滤波实现过程纪要(欢迎挑战)
    自从何凯明提出导向滤波后,因为其算法的简单性和有效性,该算法得到了广泛的应用,以至于新版的matlab都将其作为标准自带的函数之一了&#x ... [详细]
  • 解读基因集富集分析(GSEA)结果及应用
    本文详细介绍了基因集富集分析(Gene Set Enrichment Analysis, GSEA)的基本原理,以及如何通过GSEA分析结果来解析基因表达数据。此外,还提供了使用R语言进行GSEA分析的具体方法。 ... [详细]
  • 社会网络分析学习笔记 - 模块4
    本文探讨了小世界现象及其在社交网络中的应用,包括厄多斯数和培根数的概念。文章还介绍了图的基本表示方法,如边列表和邻接矩阵,并讨论了它们在不同规模网络中的适用性和效率。 ... [详细]
  • 解析Java虚拟机HotSpot中的GC算法实现
    本文探讨了Java虚拟机(JVM)中HotSpot实现的垃圾回收(GC)算法,重点介绍了根节点枚举、安全点及安全区域的概念和技术细节,以及这些机制如何影响GC的效率和准确性。 ... [详细]
  • 如何高效地将CAJ文档转换为Word格式
    在学术研究和日常工作中,我们有时需要将特定的CAJ格式文档转换为更通用的Word格式。本文将详细介绍如何轻松实现这一转换,帮助用户快速掌握操作步骤。 ... [详细]
  • 贡献转移在计算每个元素的作用的时候,我们可以通过反向枚举作用效果,添加到作用元素的身上,这种方法叫做贡献转移。更正式的说, ... [详细]
  • 本文回顾了作者在求职阿里和腾讯实习生过程中,从最初的迷茫到最后成功获得Offer的心路历程。文中不仅分享了个人的面试经历,还提供了宝贵的面试准备建议和技巧。 ... [详细]
  • 春季职场跃迁指南:如何高效利用金三银四跳槽季
    随着每年的‘金三银四’跳槽高峰期的到来,许多职场人士都开始考虑是否应该寻找新的职业机会。本文将探讨如何制定有效的职业规划、撰写吸引人的简历以及掌握面试技巧,助您在这关键时期成功实现职场跃迁。 ... [详细]
author-avatar
手机用户2602900871
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有