服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - 面试题快慢链表和快慢指针

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

2021-05-18 16:05AsuraDong C/C++

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

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

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

原文链接:http://www.cnblogs.com/AsuraDong/p/6986919.html

延伸 · 阅读

精彩推荐