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;
}
n