单链表的建立、插入等替他操作见本人博客：

单链表的基本操作 

【面试题】单链表的操作1 

介绍了4种有关单链表的面试题，对于以下链表要求的实现，解题的思路很重要。例如两个有序链表的合并，实现约瑟夫环及链表成环问题。

各函数的实现，代码如下：

SListNode* MergeList(SListNode* L1, SListNode* L2)//合并两个有序链表，合并后依然有序{//认为不带头结点的单链表，注意应判断两个链表是否为空	if (L1 == NULL)		return L2;	if (L2 == NULL)		return L1;	//if (L1 || L2)	//	return L1 = NULL ? L2 : L1;	SListNode* NewHead = NULL;	SListNode* pHead1 = L1;	SListNode* pHead2 = L2;	//进行一次比较，找出较小的值，使NewHead指向新链表的头结点	if (pHead1->data < pHead2->data)	{		NewHead = pHead1;		pHead1 = pHead1->next;	}	else	{		NewHead = pHead2;		pHead2 = pHead2->next;	}	//用tail指针进行比较和移动	SListNode* tail = NewHead;	while (pHead1 && pHead2)	{		if (pHead1->data < pHead2->data)		{			tail->next = pHead1;			pHead1 = pHead1->next;		}		else		{			tail->next = pHead2;			pHead2 = pHead2->next;		}		tail = tail->next;	}	//如果两个链表不一样长时，将其链接在新链表的后面	if (pHead1)		tail->next = pHead1;	else		tail->next = pHead2;	return NewHead;}void BubbleSort(SListNode* pHead)//冒泡排序单链表{	if (pHead == NULL || pHead->next == NULL)		return;	int exchange = 0;//标志位判断排序是否已达到有序	SListNode* tail = pHead->next;//比较n-1趟	while (tail)	{//两个指针cur，next进行比较和移动		SListNode* cur = pHead;		SListNode* next = pHead->next;		while (next)		{			if (cur->data > next->data)			{				exchange = 1;				DataType tmp = cur->data;				cur->data = next->data;				next->data = tmp;			}			cur = cur->next;			next = next->next;		}		if (exchange == 0)//如果没有发生交换，则链表已有序			break;		tail = tail->next;	}}SListNode* JosephCycle(SListNode* pHead, int k)//单链表实现约瑟夫环{//判断链表及k是否有效	if (pHead == NULL || k <= 0)		return NULL;	SListNode* cur = pHead;	while (1)	{		if (cur->next == cur)			return cur;		int count = k;		while (--count)			cur = cur->next;		//替换法删除结点		SListNode* next = cur->next;		cur->data = next->data;		cur->next = next->next;		free(next);	}	return NULL;}//判断单链表是否带环？若带环，求环长度，求环入口点SListNode* CheckCycle(SListNode* pHead)//检查是否带环{//利用快慢指针，慢指针走一步，快指针走两步；如果存在环，两个指针一定会相遇。	if (pHead == NULL || pHead->next == NULL)		return NULL;	SListNode* slow = pHead;	SListNode* fast = pHead;	while (fast && fast->next)//条件为fast和fast->next都不为空	{		slow = slow->next;		fast = fast->next->next;		if (fast == slow)			return slow;//如何带环返回相遇的结点	}	return NULL;}int GetCycleLength(SListNode* MeetNode)//求环的长度{//检查是否带环，即存在相遇点，走一圈就可以求出环的长度	assert(MeetNode);	SListNode* cur = MeetNode;	int count = 0;	do	{		count++;		cur = cur->next;	} while (cur != MeetNode);	return count;}SListNode* GetEntryNode1(SListNode* pHead)//求环的入口地址{//检查是否有环，通过快慢指针分别从头结点和相遇结点处开始走，相遇点即为入口结点	if (pHead == NULL || pHead->next == NULL)		return NULL;	SListNode* meetnode = CheckCycle(pHead);	SListNode* slow = pHead;	SListNode* fast = meetnode;	while(slow && fast)	{		if (slow == fast)			return fast;		slow = slow->next;		fast = fast->next;	}	return NULL;}int SListLength(SListNode* pHead)//分别求环形链表被拆成两条链表的链表长度{	if (pHead == NULL)		return 0;	int count = 0;	SListNode* cur = pHead;	while (cur)	{		cur = cur->next;		count++;	}	return count;}SListNode* GetEntryNode2(SListNode* pHead)//求环的入口地址---两个链表相交思想{//检查是否有环，在聚点处截断，求出两个链表相交点即为入口地址	if (pHead == NULL || pHead->next == NULL)		return NULL;	SListNode* cur1 = pHead;	SListNode* cur2 = CheckCycle(pHead)->next;	CheckCycle(pHead)->next = NULL;//此法造成数据丢失	int len1 = SListLength(cur1);	int len2 = SListLength(cur2);	PrintSList(cur1);	printf("\n---------------------\n");	PrintSList(cur2);	int errand;//两个链表的长度差	//长链表先走errand步	if (len1 > len2)	{		errand = len1 - len2;		while (errand--)			cur1 = cur1->next;	}	else	{		errand = len2 - len1;		while (errand--)			cur2 = cur2->next;	}	//两个链表同步前进	while (cur1 != cur2)	{		cur1 = cur1->next;		cur2 = cur2->next;	} 	return cur2;}

各函数测试用例如下：

void Test10(){//【面试题七】合并两个有序链表，合并后依然有序	SListNode* phead1 = NULL;	SListNode* phead2 = NULL;	PushBack_Cpp(phead1, 1);	PushBack_Cpp(phead1, 3);	PushBack_Cpp(phead1, 6);	PushBack_Cpp(phead2, 2);	PushBack_Cpp(phead2, 4);	PushBack_Cpp(phead2, 5);	PushBack_Cpp(phead2, 7);	SListNode* phead = MergeList(phead1,phead2);	PrintSList(phead);	printf("\n---------------------\n");}void Test11(){//【面试题八】冒泡排序单链表	SListNode *phead = NULL;	PushBack_Cpp(phead, 4);	PushBack_Cpp(phead, 5);	PushBack_Cpp(phead, 3);	PushBack_Cpp(phead, 2);	PushBack_Cpp(phead, 6);	PushBack_Cpp(phead, 1);	PrintSList(phead);	printf("\n---------------------\n");	BubbleSort(phead);	PrintSList(phead);}void Test12(){//【面试题九】单链表实现约瑟夫环	SListNode *phead = NULL;	PushBack_Cpp(phead, 1);	PushBack_Cpp(phead, 2);	PushBack_Cpp(phead, 3);	PushBack_Cpp(phead, 4);	PushBack_Cpp(phead, 5);	PushBack_Cpp(phead, 6);	PrintSList(phead);	printf("\n---------------------\n");	Find(phead, 6)->next = Find(phead, 1);//将链表构成一个环，尾接头	SListNode* FindNode = JosephCycle(phead,3);	printf("%d\n",FindNode->data);}void Test13(){//【面试题十】判断单链表是否带环？若带环，求环长度，求环入口点	SListNode *phead = NULL;	PushBack_Cpp(phead, 1);	PushBack_Cpp(phead, 2);	PushBack_Cpp(phead, 3);	PushBack_Cpp(phead, 4);	PushBack_Cpp(phead, 5);	PushBack_Cpp(phead, 6);	PushBack_Cpp(phead, 7);	PrintSList(phead);	printf("\n---------------------\n");	Find(phead, 6)->next = Find(phead, 3);	SListNode* meetnode = CheckCycle(phead);//检查是否带环	printf("%d\n", meetnode->data);	if (meetnode==NULL)		printf("该单链表不带环！\n");	else	{		printf("该单链表带环！\n");		int len = GetCycleLength(meetnode);//求环的长度	    printf("length = %d\n", len);		SListNode* entry1 = GetEntryNode1(phead);//求环的入口地址		printf("入口处为：%d\n", entry1->data);		printf("\n---------------------\n");		SListNode* entry2 = GetEntryNode2(phead);//求环的入口地址		printf("\n入口处为：%d\n", entry2->data);	}	}int main(){	Test7();	printf("\n***********************\n");	Test8();	printf("\n***********************\n");	Test9();	printf("\n***********************\n");	Test10();	printf("\n***********************\n");	Test11();	printf("\n***********************\n");	Test12();	printf("\n***********************\n");	Test13();	system("pause");}