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

C语言经典链表面试题分享

程序员文章站 2022-06-21 20:57:42
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;
}

如上就是经典面试题的解法。灵活应用，后续会继续更新。

<

上一篇： 嘎巴虾怎么拌好吃，拌得好才是爽口的下酒菜

下一篇： ASP.NET2.0的跨页回调

推荐阅读