当前位置：首页 > 资讯 > 技术文档

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

时间：2022-03-28 08:43 编辑：来源：阅读：
扫一扫，手机访问

摘要：面试题快慢链表和快慢指针

腾讯的一道面试题：如何快速找到位置长度单链表的中间节点？普通方法，就是先遍历，在从头找到2/length的中间节点。算法复杂度是：O(3*n/2)。而更快的方法就是利用快慢指针的原理。 [b]快慢链表：利用标尺的思想，设置两个指针（一快一慢）*serach和*mid，刚开始都指向单链表的头结点。但是*search指针的移动速度是*mid的两倍。当*search到尾结点的时候，mid刚好到了中间。算法复杂度是：O(n/2)[/b]

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;
}

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

全部评论(0)

上一篇：new和malloc的区别深入解析
下一篇：C语言数据结构树的双亲表示法实例详解

资讯排行榜
更多>>