当前位置： 移动技术网 > IT编程>开发语言>C/C++ > C语言经典链表面试题分享

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

2018年02月08日  | 移动技术网IT编程  | 我要评论

中国商信网,家用净水器 浩泽官网,狂龙傲宇

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

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

<

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网