加入收藏 | 设为首页 | 会员中心 | 我要投稿 PHP编程网 - 黄冈站长网 (http://www.0713zz.com/)- 数据应用、建站、人体识别、智能机器人、语音技术!
当前位置: 首页 > 创业 > 经验 > 正文

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

发布时间:2021-01-09 14:24:38 所属栏目:经验 来源:网络整理
导读:腾讯的一道面试题:如何快速找到位置长度单链表的中间节点?普通方法,就是先遍历,在从头找到2/length的中间节点。算法复杂度是:O(3*n/2)。而更快的方法就是利用快慢指针的原理。 快慢链表:利用标尺的思想,设置两个指针(一快一慢)*serach和*mid,刚

腾讯的一道面试题:如何快速找到位置长度单链表的中间节点?普通方法,就是先遍历,在从头找到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;
} 

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

(编辑:PHP编程网 - 黄冈站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读