当前位置 : IT培训网 > 求职攻略 > 列举C语言链表面试题及答案

列举C语言链表面试题及答案

时间:2019-10-17 14:08:30  来源:编程网  作者:IT培训网  已有:名学员访问该课程
C语言对于一些学习者来说,或都会觉得很难,想从事C语言工程师的面试恐怕是最能过的一关,C语言经常会涉及到一些面试难点,这里,我们就从一些常见的经典C语言面试入手,IT培训网汇总并解析一些C语言面试题,如替换法,快慢指针等等,希望对C语言求职面试有所帮助。

C语言对于一些学习者来说,或都会觉得很难,想从事C语言工程师的面试恐怕是最能过的一关,C语言经常会涉及到一些面试难点,这里,我们就从一些常见的经典C语言面试入手,IT培训网汇总并解析一些C语言面试题,如替换法,快慢指针等等,希望对C语言求职面试有所帮助。

列举C语言链表面试题及答案_www.cnitedu.cn

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

}

面试题十一:判断是否带环

SListNode* SListIsCycle(SListNode* list)//11.判断是否带环

{

SListNode *cur,*fast;

cur=fast=list;

while (fast && fast->next)

{

cur=cur->next;

fast=fast->next->next;

if (fast==cur)

{

return cur;

}

}

return NULL;

}

面试题十二:求环的长度

int SListCycleLen(SListNode* meetNode)//12.求环的长度

{

int n=1;

SListNode *cur=meetNode;

while(cur->next!=meetNode)

{

++n;

cur=cur->next;

}

return n;

}

面试题十三:求环的入口点(环的入口点就是一个从链表开始另一个从相遇点开,当他们相交的点就是入口点)

SListNode* SListCrossEntreNode(SListNode* list, SListNode* meetNode) //13.求环的入口点(环的入口点就是一个从链表开始另一个从相遇点开,当他们相交的点就是入口点)

{

while (list!=meetNode)

{

list=list->next;

meetNode=meetNode->next;

}

return list;

}

面试题十四:判断两个链表是否相交。(假设链表不带环)

int SListIsCrossNode(SListNode* list1, SListNode* list2)//14.判断两个链表是否相交,若相交,求交点。(假设链表不带环)

{

while (list1 && list1->next)

{

list1=list1->next;

}

while(list2 &&list2->next)

{

list2=list2->next;

}

if (list2==list1 && list1!=NULL)

{

return 1;

}

return 0;

}

面试题十四(2):两个链表相交,求交点。

SListNode *SListEnterNode(SListNode* list1,SListNode* list2)//两个链表相交,求交点。

{

SListNode *cur1=list1;

SListNode *cur2=list2;

int n1=0;

int n2=0;

while (cur1->next)

{

n1++;

cur1=cur1->next;

}

while (cur2->next)

{

n2++;

cur2=cur2->next;

}

cur1=list1;

cur2=list2;

if (n1-n2 >=0)

{

while (n1-n2!=0)

{

cur1=cur1->next;

n1--;

}

while (cur1!=cur2)

{

cur1=cur1->next;

cur2=cur2->next;

}

}

else

{

while (n2-n1!=0)

{

cur2=cur2->next;

n2--;

}

while (cur1!=cur2)

{

cur1=cur1->next;

cur2=cur2->next;

}

}

return cur1;

}

测试代码:

void Test1()//1.从尾到头打印单链表

{

SListNode *a=NULL;

SListPushBack(&a,1);

SListPushBack(&a,2);

SListPushBack(&a,3);

SListPushBack(&a,4);

SListPushBack(&a,5);

SListPrint(a);

SLitsPrintTailToHead(a);//非递归 时间复杂度n平方

SListPrintTailToHeadR(a);//递归

}

void Test2()//2.删除一个无头单链表的非尾节点(不能遍历链表)

{

SListNode *a=NULL;

SListNode *pos=NULL;

SListPushBack(&a,1);

SListPushBack(&a,2);

SListPushBack(&a,3);

SListPushBack(&a,4);

SListPushBack(&a,5);

SListPrint(a);

pos=SListFind(a,3);

SListDelNonTailNode(pos);

SListPrint(a);

}

void Test3()//3.在无头单链表的一个节点前插入一个节点(不能遍历链表)

{

SListNode *a=NULL;

SListNode *pos=NULL;

SListPushBack(&a,1);

SListPushBack(&a,2);

SListPushBack(&a,3);

SListPushBack(&a,4);

SListPushBack(&a,5);

SListPrint(a);

pos=SListFind(a,3);

SListInsertFrontNode(pos,8);

SListPrint(a);

}

void Test4()//4.单链表实现约瑟夫环(JosephCircle)

{

SListNode* list = NULL;

SListNode* tail;

SListPushBack(&list, 1);

SListPushBack(&list, 2);

SListPushBack(&list, 3);

SListPushBack(&list, 4);

SListPushBack(&list, 5);

tail = SListFind(list, 5);

tail->next = list;

printf("最后的幸存者:%d\n", SListJosephCircle(list, 3)->data);

}

void Test5()//5.//逆置/反转单链表

{

SListNode* list = NULL;

SListNode* newList;

SListPushBack(&list, 1);

SListPushBack(&list, 2);

SListPushBack(&list, 3);

SListPushBack(&list, 4);

SListPushBack(&list, 5);

newList = SListReverse(list);

SListPrint(newList);

}

void Test6()//6.单链表排序(冒泡排序&快速排序)

{

SListNode* list = NULL;

SListPushBack(&list, 1);

SListPushBack(&list, 22);

SListPushBack(&list, 33);

SListPushBack(&list, 40);

SListPushBack(&list, 5);

SListBubbleSort(list);

SListPrint(list);

}

void Test7()//7.合并两个有序链表,合并后依然有序

{

SListNode *a=NULL;

SListNode *b=NULL;

SListNode *c=NULL;

SListPushBack(&a,1);

SListPushBack(&a,2);

SListPushBack(&a,3);

SListPushBack(&a,4);

SListPushBack(&a,5);

SListPushBack(&a,7);

SListPushBack(&a,9);

SListPushBack(&b,2);

SListPushBack(&b,2);

SListPushBack(&b,3);

SListPushBack(&b,4);

SListPushBack(&b,5);

c=SListMerge(a,b);

SListPrint(c);

}

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

{

SListNode *a=NULL;

SListNode *b=NULL;

SListPushBack(&a,1);

SListPushBack(&a,2);

SListPushBack(&a,3);

SListPushBack(&a,4);

SListPushBack(&a,5);

b=SListFindMidNode(a);

SListPrint(b);

}

void Test9()//9.查找单链表的倒数第k个节点,要求只能遍历一次链表

{

SListNode *a=NULL;

SListNode *b=NULL;

SListPushBack(&a,1);

SListPushBack(&a,2);

SListPushBack(&a,3);

SListPushBack(&a,4);

SListPushBack(&a,5);

b=SListFindTailKNode(a,2);

SListPrint(b);

}

void Test10()//10.删除链表的倒数第K个结点

{

SListNode *a=NULL;

SListNode *b=NULL;

SListPushBack(&a,1);

SListPushBack(&a,2);

SListPushBack(&a,3);

SListPushBack(&a,4);

SListPushBack(&a,5);

SListFindPop(a,3);

SListPrint(a);

}

void Test11_12_13()//11.判断是否带环 12.求环的长度 13。求环的入口点

{

SListNode *a=NULL;

SListNode *enter=NULL;

SListNode *tail=NULL;

SListNode *cur=NULL;

SListPushBack(&a,1);

SListPushBack(&a,2);

SListPushBack(&a,3);

SListPushBack(&a,4);

SListPushBack(&a,5);

tail=SListFind(a,5);//构建带环

enter=SListFind(a,3);

tail->next=enter;

cur=SListIsCycle(a);

printf("是否带环:%d\n",cur->data);

printf("环长度为:%d\n",SListCycleLen(cur));

printf("环入口点为:%d\n",SListCrossEntreNode(a,cur)->data);

}

void Test14()//14。判断两个链表是否相交,若相交,求交点。(假设链表不带环)

{

SListNode *a,*b;

SListNode *n1=BuySListNode(1);

SListNode *n2=BuySListNode(2);

SListNode *n3=BuySListNode(3);

SListNode *n4=BuySListNode(4);

a=BuySListNode(7);

b=BuySListNode(8);

n1->next=n2;

n2->next=n3;

n3->next=n4;

a->next=b;

b->next=n3;

printf("是否带环:%d \n",SListIsCycle(a,n1));

printf("环的入口点为:%d \n",SListEnterNode(a,n1)->data);

}

主函数:

int main()

{

//Test1();

//Test2();

//Test3();

//Test4();

//Test5();

//Test6();

//Test7();

//Test8();

//Test9();

//Test10();

//Test11_12_13();

Test14();

system("pause");

return 0;

}

如上就是经典面试题的解法,想在C语言方面发展的程序员,可以收藏一下,对于将来的面试有所准备。

顶一下
(0)
0%
踩一下
(0)
0%

IT培训0元试听 每期开班座位有限.0元试听抢座开始! IT培训0元试听

  • 姓名 : *
  • 电话 : *
  • QQ : *
  • 留言 :
  • 验证码 : 看不清?点击更换请输入正确的验证码

在线咨询在线咨询

温馨提示 : 请保持手机畅通,咨询老师为您
提供专属一对一报名服务。

------分隔线----------------------------
------分隔线----------------------------

推荐内容

相关热点