欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

快慢链表和快慢指针

程序员文章站 2023-08-29 18:03:21
快慢链表和快慢指针。腾讯的一道面试题:如何快速找到位置长度单链表的中间节点?普通方法,就是先遍历,在从头找到2/length的中间节点。算法复杂度是:o(3*n/2)。而更快的方法就是利用快慢指针的...

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