宁波Java培训
达内宁波中心

13732203138

热门课程

10个C语言链表的面试题,经典

  • 时间:2018-02-27 14:22
  • 发布:转载
  • 来源:网络

C语言诸多面试题,这里有常用的经典面试题,应用有多种算法,如替换法,快慢指针等等。

面试题 一:从尾到头打印单链表。

void SLitsPrintTailToHead(SListNode* pHead)//非递归算法(利用俩个指针一个定义到尾部p1,另一个定义到头开始循环p2,每当p2循环到尾部时,输出p2的值,让尾部p1指向p2.再次开始循环,以此往复。)

{

 

    SListNode *cur=NULL;

    while (cur!=pHead)

    {

        SListNode *tail=pHead;

        while(tail->next!=cur)

        {

            tail=tail->next;

        }

        printf("%d ",tail->data);

        cur=tail;

    }

 

}

void SListPrintTailToHeadR(SListNode* pHead)//递归算法

{

    if (pHead==NULL)

    {

        return;

    }

    SListPrintTailToHeadR(pHead->next);

    printf("%d ",pHead->data);

}

面试题二:删除一个无头单链表的非尾节点(不能遍历链表)

void SListDelNonTailNode(SListNode* pos)//应用了向前替换法,把后一个的值赋值给pos替换原值,然后把pos指向pos下一个的下一个。

{

     SListNode *cur=NULL;

     cur=pos->next;

     pos->data=cur->data;

     pos->next=cur->next;

     free(cur);

}


面试题三:在无头单链表的一个节点前插入一个节点(不能遍历链表)

void SListInsertFrontNode(SListNode* pos, DataType x)

{

    SListNode *cur=BuySListNode(pos->data);

    cur->next=pos->next;

    pos->data=x;

    pos->next=cur;

     

}


面试题四:单链表实现约瑟夫环(JosephCircle)

///// 4.单链表实现约瑟夫环(JosephCircle) ////////////约瑟夫环就比如说一群人围成一个圈,从一个人开始报数,如报到3的人就退出,下一个继续从1开始,直到只剩一个人时结束。

SListNode* SListJosephCircle(SListNode* pHead, int k)//phead是一个循环链表 

{

    SListNode *cur=pHead;

    SListNode *nx=NULL;

    while(cur->next!=cur)

    {

        int Coun=k;

        while (--Coun)

        {

            cur=cur->next;

        }

        nx=cur->next;//利用替换法不需要遍历链表进行删除节点

        cur->data=nx->data;

        cur->next=nx->next;

        free(nx);

    }

    return cur;

}


面试题五:逆置/反转单链表

SListNode* SListReverse(SListNode* list)//逆置/反转单链表 (重要多看看)

{

    SListNode *cur=list;

    SListNode *newlist=NULL;

    SListNode *_next=NULL;

    while (cur)

    {

        _next=cur->next;

        cur->next=newlist;

        newlist=cur;

        cur=_next;

    }

    return newlist;

}


面试题六:单链表排序(冒泡排序&快速排序)

void SListBubbleSort(SListNode* list)//单链表排序(冒泡排序&快速排序) 冒泡排序俩俩比较。

{

    SListNode *tail=NULL;

    while (list!=tail)

    {

        int change=0;

        SListNode *cur=list;

        SListNode *_next=list->next;

        while (_next!=tail)

        {

            if (cur->data > _next->data)

            {

                DataType tmp=cur->data;

                cur->data=_next->data;

                _next->data=tmp;

                change=1;

            }

            _next=_next->next;

            cur=cur->next;

        }

        if (change==0)

        {

            break;

        }

        tail=cur;

    }

}


面试题七:合并两个有序链表,合并后依然有序

SListNode* SListMerge(SListNode* list1, SListNode* list2)//合并两个有序链表,合并后依然有序 

{

    SListNode *newlist=NULL;//

    SListNode *list=NULL;

    if (list2==NULL)

    {

        return list1;

    }

    if (list1==NULL)

    {

        return list2;

    }

    if (list1->data < list2->data)

    {

        newlist=list=list1;//一个用来定位头,另一个用来遍历,返回时要返回头的指针才能遍历全部链表

        list1=list1->next;

    }

    else

    {

        newlist=list=list2;

        list2=list2->next;

    }

    while (list1&&list2)

    {

        if (list1->data < list2->data)

        {

            newlist->next=list1;

            list1=list1->next;

        }

        else

        {

            newlist->next=list2;

            list2=list2->next;

        }

        newlist=newlist->next;

    }

    if (list1)

    {

        newlist->next=list1;

    }

    if (list2)

    {

        newlist->next=list2;

    }

    return list;

}


面试题八:查找单链表的中间节点,要求只能遍历一次链表

SListNode* SListFindMidNode(SListNode* list)//8.查找单链表的中间节点,要求只能遍历一次链表 

{

    SListNode *cur=NULL;//应用了快慢指针,快指针的速度是慢指针二倍,当快指针走到NULL时,慢指针所指的就是中间节点。

    SListNode *fast=NULL;

    cur=fast=list;

    while (fast && fast->next)

    {

        cur=cur->next;

        fast=fast->next->next;

    }

    return cur;

}


面试题九:查找单链表的倒数第k个节点,要求只能遍历一次链表

SListNode* SListFindTailKNode(SListNode* list, size_t k)//9.查找单链表的倒数第k个节点,要求只能遍历一次链表 

{

    SListNode *cur,*fast;//一样用了快慢指针

    cur=fast=list;

    while(k--)

    {

        if (fast==NULL)

        {

            return 0;

        }

        fast=fast->next;

    }

    while(fast)

    {

        fast=fast->next;

        cur=cur->next;

    }

    return cur;

}


面试题十:删除链表的倒数第K个结点

void SListFindPop(SListNode *list,size_t k)//10.删除链表的倒数第K个结点 

{

    SListNode *cur=NULL;

    SListNode *tail=list;

    cur=SListFindTailKNode(list,k);

    while(list->next!=cur)

    {

        list=list->next;

    }

    list->next=cur->next;

    free(cur);

}

预约申请免费试听课

怕钱不够?就业挣钱后再付学费!    怕学不会?从入学起,达内定制课程!     担心就业?达内多家实践企业供你挑选 !

上一篇:更新Java面试题整理,拿offer全靠它了
下一篇:苹果公司刁钻的面试题,有种就来挑战!

Java集合类面试题总结

Java面试常问的题目+解答分享

Java面试题之你对Java平台的理解

java面试题之简述springMVC的执行流程

选择城市和中心
贵州省

广西省

海南省