C语言经典链表面试题分享
程序员文章站
2022-03-23 20:48:37
C语言诸多面试题,这里有常用的经典面试题,应用有多种算法,如替换法,快慢指针等等。 注:含有的有关头文件引用上一篇博客单链表的插与删,本篇文章不在写出。
面试题 一:从尾到头打印...
C语言诸多面试题,这里有常用的经典面试题,应用有多种算法,如替换法,快慢指针等等。 注:含有的有关头文件引用上一篇博客单链表的插与删,本篇文章不在写出。
面试题 一:从尾到头打印单链表。
/////// 1.从尾到头打印单链表 ////////// 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; }