面试题快慢链表和快慢指针
腾讯的一道面试题:如何快速找到位置长度单链表的中间节点?普通方法,就是先遍历,在从头找到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; }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
您可能感兴趣的文章
- 01-10探讨:用两个栈实现一个队列(我作为面试官的小结)
- 01-10C++ 创建桌面快捷方式 开始菜单的实现代码
- 01-10C与C++ 无参函数的区别解析
- 01-10浅析c/c++中函数的参数传递
- 01-10c字符串,string对象,字符串字面值的区别详解
- 01-10全面解析C++中的new,operator new与placement new
- 01-10shared_ptr线程安全性全面分析
- 01-10头文件不宜定义变量的原因全面解析
- 01-10关于C++中的static关键字的总结
- 01-10C++对象的动态建立与释放详解


阅读排行
本栏相关
- 04-02c语言函数调用后清空内存 c语言调用
- 04-02func函数+在C语言 func函数在c语言中
- 04-02c语言的正则匹配函数 c语言正则表达
- 04-02c语言用函数写分段 用c语言表示分段
- 04-02c语言中对数函数的表达式 c语言中对
- 04-02c语言编写函数冒泡排序 c语言冒泡排
- 04-02c语言没有round函数 round c语言
- 04-02c语言分段函数怎么求 用c语言求分段
- 04-02C语言中怎么打出三角函数 c语言中怎
- 04-02c语言调用函数求fibo C语言调用函数求
随机阅读
- 01-10C#中split用法实例总结
- 04-02jquery与jsp,用jquery
- 01-11Mac OSX 打开原生自带读写NTFS功能(图文
- 08-05织梦dedecms什么时候用栏目交叉功能?
- 01-11ajax实现页面的局部加载
- 01-10SublimeText编译C开发环境设置
- 08-05DEDE织梦data目录下的sessions文件夹有什
- 08-05dedecms(织梦)副栏目数量限制代码修改
- 01-10使用C语言求解扑克牌的顺子及n个骰子
- 01-10delphi制作wav文件的方法