链表相关问题

发表于： 2018-07-25 分类于：数据结构与算法

字数： 6206 阅读：≈ 13分钟浏览：评论：

题目一

题目一：假设有如下的复杂链表，每个节点都有next指针和random指针，random指针是随机指向，请完成这条复杂链表的复制！

定义复杂链表节点

typedef struct ComplexNode
{
	DataType _data;
	struct ComplexNode* _next;
	struct ComplexNode* _random;
} ComplexNode;

需要的功能

//产生新节点
ComplexNode* BuyComplexNode(DataType x);

//打印此复杂链表
void PrintComplexList(ComplexNode* plist);

//复制复杂链表
ComplexNode* CopyList(ComplexNode* list);

复制链表的图片分析

绿色箭头便是random指针，指向任意，那么如何来复制这条复杂链表呢？

思路说明

1、先先断开原有链表，插入新节点，如图所示：5后面插入新节点5，4后面插入新节点4，….新节点1后面补成NULL 2、复制随机指针，这里的随机指针如何才能找到之前的random指针的指向呢？很简单，原来的节点的random指针指向的节点的next所指向的地方就是新节点的random指向应该指向的地方，这样我们就可以很方便的完成随机指针指向的复制 3、分离两条链表，这个也是比较容易的，让一个指针连续走两步，执行链接！

//复杂链表的复制。
ComplexNode* BuyComplexNode(DataType x)
{
	ComplexNode* node = (ComplexNode*)malloc(sizeof(ComplexNode));
	assert(node);
	node->_next = NULL;
	node->_random = NULL;
	node->_data = x;
	return node;
}

//打印这个复杂链表
void PrintComplexList(ComplexNode* plist)
{
	ComplexNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d:", cur->_data);
		if (cur->_random != NULL)
			printf("(%d)-->", cur->_random->_data);
		else
		{
			printf("(NULL)-->");
		}
		cur = cur->_next;
	}
	printf("Over\n");
}
//实现复制链表，返回复制后的新链表。
ComplexNode* CopyList(ComplexNode* list)
{
	//1、在当前节点的后面插入一个当前节点的数据
	ComplexNode* cur = list;
	ComplexNode* newlist = NULL;
	ComplexNode* cp = NULL;
	ComplexNode* next = list->_next;

	assert(list != NULL);

	while (cur != NULL)
	{
		ComplexNode* newNode = BuyComplexNode(cur->_data);
		newNode->_next = next;
		cur->_next = newNode;
		cur = next;
		if (next != NULL)
			next = cur->_next;
	}
	//2、调整插入节点的random指针
	cur = list;
	cp = cur->_next;
	while (cur != NULL)
	{
		if (cur->_random != NULL)
			cp->_random = cur->_random->_next;
		cur = cp->_next;
		if (cur != NULL)
			cp = cur->_next;
	}
	//3、拆除链表
	cur = list;
	cp = cur->_next;

	//确定新链表的起始位置
	newlist = cp;

	while (cur != NULL)
	{
		cur->_next = cp->_next;
		if (cur->_next != NULL)
			cp->_next = cur->_next->_next;
		cur = cur->_next;
		cp = cp->_next;
	}

	return newlist;
}

测试用例

void test()
{
	ComplexNode* plist  = NULL;
	ComplexNode* newlist = NULL;

	ComplexNode* p1 = BuyComplexNode(5);
	ComplexNode* p2 = BuyComplexNode(4);
	ComplexNode* p3 = BuyComplexNode(3);
	ComplexNode* p4 = BuyComplexNode(2);
	ComplexNode* p5 = BuyComplexNode(1);
	plist = p1;
	p1->_next = p2;
	p2->_next = p3;
	p3->_next = p4;
	p4->_next = p5;
	p5->_next = NULL;

	p1->_random = p3;
	p2->_random = p1;
	p3->_random = NULL;
	p4->_random = p2;
	p5->_random = p4;

	printf("原表：");
	PrintComplexList(plist);
	newlist = CopyList(plist);

	printf("新表：");
	PrintComplexList(newlist);
	printf("原表：");
	PrintComplexList(plist);
}

效果演示

题目二

题目二：两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的！如下图所示：

注意问题

这是一个经常被各公司采用的面试题，最容易犯两种错误：

一是在写代码时没有对合并的过程想清楚，导致合并出来的链表不是想要的结果！
二是代码的鲁棒性存在问题，程序一旦有特殊的链表就会崩溃

合并思路

1、先考虑考虑特殊情况，包括输入空链表，两条链表是同一条链表等等情况需要在一开始就考虑好 2、确定新链表的头结点，谁小就把谁当做头结点 3、使用一个指针来维护尾节点，方便尾部插入元素，每插入一个元素就向后移动 4、谁小就把谁插到尾部，然后继续比较 5、注意其中任何一条链表结束不要忘记另一条还没有结束的链表，要在尾部补上

//合并两个有序链表,合并后依然有序 
pList Merge(pList list1, pList list2)
{
	pList newlist = NULL;
	//tail表示链表的尾部
	pNode tail = NULL;

	//先考虑特殊情况
	if (list1 == list2)
		return NULL;
	if (list1 == NULL)
		return list2;
	if (list2 == NULL)
		return list1;

	//确定头节点
	if (list1->data < list2->data)
	{
		newlist = list1;
		list1 = list1->next;
	}
	else{
		newlist = list2;
		list2 = list2->next;
	}

	//两条链表中找较小的元素尾插
	tail = newlist;
	while ((list1 != NULL) && (list2 != NULL))
	{
		if (list1->data < list2->data){
			tail->next = list1;
			list1 = list1->next;
		}
		else{
			tail->next = list2;
			list2 = list2->next;
		}
		tail = tail->next;
	}
	//能走到这里说明其中一条链表已经结束了
	if (list1 == NULL)
	{
		tail->next = list2;
	}
	else{
		tail->next = list1;
	}
	return newlist;
}

测试用例

void test()
{
	int i = 0;
	pList plist1 = NULL;
	pList plist2 = NULL;
	pList plist3 = NULL;
	InitList(&plist1);
	InitList(&plist2);
	for (i = 0; i <= 10; i++)
	{
		if (i % 2 == 0)
			PushBack(&plist1, i);
		else
		{
			PushBack(&plist2, i);
		}
	}
	PushBack(&plist1, 12);
	PushBack(&plist1, 13);
	PrintList(plist1);
	PrintList(plist2);

	plist3 = Merge(plist1, plist2);
	PrintList(plist3);
}

递归的方式更易理解

其实很容易看出来，只要确定了第一个节点，我们可以把它看成是第一个节点与剩下两条链表的合并结果的合并，这样的话只需要有限次的递归便可以完成这个看似复杂的问题！

//递归写法
pNode Merge_R(pList list1, pList list2)
{
	pList newlist = NULL;

	//先考虑特殊情况
	if (list1 == list2)
		return NULL;
	if (list1 == NULL)
		return list2;
	if (list2 == NULL)
		return list1;

	//确定头结点
	if (list1->data < list2->data)
	{
		newlist = list1;
		list1->next = Merge_R(list1->next, list2);
	}
	else
	{
		newlist = list2;
		list2->next = Merge_R(list2->next, list1);
	}
	return newlist;
}

考点

考察分析问题能力，考察指针操作能力，应该透彻分析问题形成清晰的思路，才能够写出正确的代码！
考察代码的鲁棒性，需要考虑到很多特殊操作，尤其是空指针的情况和空链表的情况处理！

题目三

题目三：现给出两个有序单链表，求出这两条链表的交集

函数实现结果演示

这个总体思路也是比较简单的，既然是有序的，那么就可以直接根据大小比对，大的节点先放着，小的往后走看能否遇到和大的节点一样的data，相等的话就直接输出，这样每一个元素都不会漏掉了！

//求两个有序单链表交集(差集)
void UnionSet(pList list1, pList list2)
{
	if (list1 == NULL || list2 == NULL)
		return;
	while (list1 && list2)
	{
		if (list1->data < list2->data)
		{
			list1 = list1->next;
		}
		else if (list1->data > list2->data)
		{
			list2 = list2->next;
		}
		else
		{
			printf("%d ", list1->data);
			list1 = list1->next;
			list2 = list2->next;
		}
	}
}

根据这个思路求差集也是很简单的，只需要把data不相等的节点的值输出就可以了！

题目四

题目四：判断两个链表是否相交，若相交，求交点。（假设链表不带环）

假设这就是两条相交的链表，交点为5，现给出两条链表的头结点plist1和plist2，求出交点：

首先判断两条链表是否相交

两条相交的链表只能是 V 字形状或者 Y 字形，所以遍历最后肯定是同一个节点，由此便可以得出两条链表是否相交，还是要注意特殊情况下的判断，保证代码的鲁棒性！

//判断两个链表是否相交，若相交，求交点。（假设链表不带环） 
int CheckCross(pList list1, pList list2)
{
	pNode end1 = NULL;
	pNode end2 = NULL;
	//任意一个为空指针就不可能相交
	if (list1 == NULL || list2 == NULL)
		return 0;
	end1 = list1;
	end2 = list2;

	while (end1->next != NULL)
		end1 = end1->next;

	while (end2->next != NULL)
		end2 = end2->next;
	
	return end1 == end2;
}

题目五

返回两条相交链表的交点

这个也不难，思路就是看两条链表谁更长，让较长的先走（长链表的长度-短链表的长度的绝对值）步，这样再同时开始走，直到地址相同的时候肯定就是交点！

//相交的话返回交点
pNode GetGrossNode(pList list1, pList list2)
{
	int len1 = 0;
	int len2 = 0; 
	//长度之差
	int gap = 0;

	pNode p1 = list1;
	pNode p2 = list2;

	//先求出两条链表的长度
	while (p1 != NULL)
	{
		len1++;
		p1 = p1->next;
	}
	while (p2 != NULL)
	{
		len2++;
		p2 = p2->next;
	}
	gap = abs(len1 - len2);

	//让较长的链表先走gap步
	if (len1 > len2){
		while (gap--)
			list1 = list1->next;
	}
	else
	{
		while (gap--)
			list2 = list2->next;
	}

	//两个链表同时开走，只要遇到地址一样的节点那么就是相交的点
	while (list1 != NULL)
	{
		list1 = list1->next;
		list2 = list2->next;
		if (list1 == list2)
			return list1;
	}
	return NULL;
}

题目六

题目六：判断单链表是否带环？

这个问题比较容易解决，我们只需要使用快慢指针的方式便可以解决该问题，快指针(一次走两步)、慢指针一次走一步，如果链表带环这两个指针肯定会相遇，由于快指针走了两步，所以还是要考虑到节点个数是奇数还是偶数，所以【fast->next != NULL】也是要判断的！

//不带环返回NULL，带环返回相遇点
pNode CheckCycle(pList plist)
{
	pNode fast = plist;
	pNode slow = plist;
	if (plist == NULL)
		return NULL;
	while ((fast != NULL) && (((fast->next) != NULL)))
	{
		fast = fast->next->next;
		slow = slow->next;
		if (fast == slow)
			return fast;
	}
	return NULL;
}

题目七

问题七：求链表的环的长度，参数为相遇点**

从相遇点的下一个节点开始计数，直到重新回到相遇点即是换的长度！

//求环的长度，参数为相遇点
int GetCircleLength(pNode meet)
{

	pNode cur = NULL;
	int len = 1;

	assert(meet != NULL);
	assert(meet->next != NULL);

	cur = meet->next;

	while (cur != meet)
	{
		len++;
		cur = cur->next;
	}
	return len;
}

题目八

题目八：求入口点位置，参数为相遇点

这个相对前面两个来说比较难想，假设不带环的部分长度是x，从入口点到两个指针的相遇点的长度为y，环的长度为L，我们可以得到如图所示的公式

即慢指针走的步数乘以2就是快指针走的距离，我们可以得出x+y是个常数K*L（也就是k个环的长度），则x总是环的长度的倍数减去y，也就是说慢指针一个从链表的起始位置走，另一个慢指针从相遇点开始走，它们总会在入口点相遇！

//求入口点，参数为相遇点
pNode GetCycleEntryNode(pList list, pNode meetNode)
{
	pList cur = list;
	if (list == NULL)
		return NULL;
	if (meetNode == NULL)
		return NULL;

	while (cur != meetNode)
	{
		cur = cur->next;
		meetNode = meetNode->next;
	}
	return cur;	
}

测试用例

void test()
{
	int i = 0;
	pList plist = NULL;
	pNode pos = NULL;
	pNode entrance = NULL;
	InitList(&plist);
	for (i = 1; i <= 5; i++)
	{
		PushBack(&plist, i);
	}
	
	//带环
	Find(plist, 5)->next = Find(plist, 3);

	pos = CheckCycle(plist);
	if (pos != NULL){
		printf("带环，相遇点为 = %d\n", pos->data);
		printf("环的长度是：%d\n", GetCircleLength(pos));
		entrance = GetCycleEntryNode(plist, pos);
		printf("环的入口点是：%d\n", entrance->data);
	}
	else
	{
		printf("不带环\n");
	}
}

题目九

题目九：查找单链表的中间节点，要求只能遍历一次链表

这个思路比较简单，利用快慢指针法即可，一个快指针【一次走两步】，一个慢指针【一次走一步】，只要快指针走到结束为止，慢指针恰好就在链表的中间！只不过快指针一次走两步，需要考虑链表元素个数为奇数个的问题，所以结束标志不只是快指针走到NULL位置，快指针的NEXT走到NULL也算是结束：

pNode FindMidNode(pList head)
{
	pNode fast = head;
	pNode slow = head;
	if (head == NULL || head->next == NULL)
		return head;
	
	while ((fast != NULL) && (fast->next != NULL))
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}

题目十

题目十：查找单链表的倒数第k个节点，要求只能遍历一次链表

这个与上面的查找中间节点的方式是一样的，也是使用两个指针只不过这次都是使用慢指针的方式，让一个指针先走k步，然后另一个指针才能开始走，直到先走的指针走到链表结尾，此时后走的指针刚好走到倒数第k个节点

//查找单链表的倒数第k个节点，要求只能遍历一次链表 
pNode FindLastKNode(pList *pplist, int k)
{
	pNode first = *pplist;
	pNode catch = *pplist;
	int num = 0;

	assert(pplist != NULL);
	if (*pplist == NULL)
		return NULL;
	while (first != NULL)
	{
		first = first->next;
		if (num++ >= k)
		{
			catch = catch->next;
		}
	}
	return catch;	
}

还是要注意特殊情况的处理！

题目十一

题目十一：冒泡排序链表

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3、针对所有的元素重复以上的步骤，除了最后一个。 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

普通的数组的冒泡排序

void fun()
{
	int arr[] = { 5, 4, 3, 2, 1 };
	int i = 0;
	int j = 0;
	int tmp = 0;
	int len = sizeof(arr) / sizeof(arr[0]);
	for (j = 0; j < len - 1; j++)
	{
		for (i = 0; i < len - 1 - j; i++)
		{
			if (arr[i] > arr[i + 1])
			{
				tmp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = tmp;
			}
		}
	}
	for (i = 0; i < len; i++){
		printf("%d ",arr[i]);
	}
}

普通数组的冒泡排序使用指针实现

void fun02()
{
	int arr[] = { 5, 4, 3, 2, 1 };
	int *start = &arr[0];
	int *start_next = start + 1;
	int *end = &arr[4];
	int tmp = 0;
	while (&arr[0] <= end)
	{
		start = &arr[0];
		start_next = start + 1;
		while (start_next < end-1)
		{
			if (*start > *start_next)
			{
				tmp = *start;
				*start = *start_next;
				*start_next = tmp;
			}
			start++;
			start_next = start + 1;
		}
		end = start;
	}
}

链表的冒泡排序

这样的话根据此方法便可以对链表进行排序了! 这个方法与使用指针对数组进行排序是一样的，只不过与之不停的地方在于数组要找到下一个元素的节点是非常容易的，对于链表可以使用next指针！

//单链表排序（冒泡排序） 
void BubbleSort(pList * pplist)
{
	pNode pCur = NULL;
	pNode pnext = NULL;
	pNode tail = NULL;
	DataType tmp = 0;

	assert(pplist != NULL);
	assert(*pplist != NULL);

	//外层循环
	while (tail != (*pplist))
	{
		pCur = *pplist;
		pnext = pCur->next;
		while (pnext != tail)
		{
			if (pCur->data > pnext->data)
			{
				tmp = pCur->data;
				pCur->data = pnext->data;
				pnext->data = tmp;
			}
			pCur = pnext;
			pnext = pnext->next;
		}
		//tail指针前移
		tail = pCur;
	}
}

优化

如果是空链表或者只有一个元素的链表则不进行排序
如果某一趟排完之后就有序，那么直接跳出循环不再排序

//单链表排序（冒泡排序） 
void BubbleSort(pList * pplist)
{
	pNode pCur = NULL;
	pNode pnext = NULL;
	pNode tail = NULL;
	DataType tmp = 0;

	//冒泡排序算法优化，定义标志位
	int flag = 0;

	assert(pplist != NULL);
	//只有一个元素或者是空链表时候不进行排序
	if (*pplist == NULL || (*pplist)->next == NULL)
		return;

	//外层循环
	while (tail != (*pplist))
	{
		pCur = *pplist;
		pnext = pCur->next;
		while (pnext != tail)
		{
			if (pCur->data > pnext->data)
			{
				//交换了之后修改标志位
				flag = 1;
				tmp = pCur->data;
				pCur->data = pnext->data;
				pnext->data = tmp;
			}
			pCur = pnext;
			pnext = pnext->next;
		}
		//tail指针前移
		tail = pCur;

		if (flag == 0) //未经改变的时候直接跳出循环
			break;
	}
}

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

题目十二

题目十二：查找单链表的中间节点，要求只能遍历一次链表

pNode FindMidNode(pList head)
{
	pNode fast = head;
	pNode slow = head;
	if (head == NULL || head->next == NULL)
		return head;
	
	while ((fast != NULL) && (fast->next != NULL))
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}

题目十三

题目十三：查找单链表的倒数第k个节点，要求只能遍历一次链表

//查找单链表的倒数第k个节点，要求只能遍历一次链表 
pNode FindLastKNode(pList *pplist, int k)
{
	pNode first = *pplist;
	pNode catch = *pplist;
	int num = 0;

	assert(pplist != NULL);
	if (*pplist == NULL)
		return NULL;
	while (first != NULL)
	{
		first = first->next;
		if (num++ >= k)
		{
			catch = catch->next;
		}
	}
	return catch;	
}

还是要注意特殊情况的处理！

题目十四

题目十四：约瑟夫环问题

约瑟夫环：JosephCycle，约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

图片示例

这样如何往复的淘汰直到只剩下最后一个人为幸存者，使用链表即可完成：

void test(){
	pList plist = NULL;
	pNode pos = NULL;
	int i = 0;
	InitList(&plist);
	for (i = 1; i <= 41; i++){
		PushBack(&plist, i);
	}
	//形成环
	pos = Find(plist, 41);
	pos->next = plist;

	//求出41个人中最后两名幸存者
	pos = JosephCycle(&plist, 3);
	printf("%d ", pos->data);//16
	printf("%d ", pos->next->data);//31
}

//单链表实现约瑟夫环 
pNode JosephCycle(pList * pplist, int num)
{
	pNode pCur = NULL;
	pNode del = NULL;
	int count = 0;

	assert(pplist != NULL);
	assert(num >= 2);

	pCur = *pplist;

	while (pCur->next->next != pCur)
	{
		count = num;
		while (--count)
		{
			pCur = pCur->next;
		}
		EraseNotTail(pCur); //根据节点位置删除节点
	}
	return pCur;
}

题目十五

题目十五：使用三指针法翻转链表

三指针毫无疑问就是使用三个指针去翻转链表，这种方式可以是我们很容易的实现链表的翻转，首先定义三个指针，分别指向第一个节点、第二个节点、第三个节点，然后由于我们保存了节点的地址，当然也就可以随心所欲的操作这些节点的指向了！

// 逆置/反转单链表 
void ReverseList(pList* pplist)
{
	pNode pCur = NULL;
	pNode tmp = NULL;
	pNode tmp2 = NULL;

	assert(pplist != NULL);
	assert(*pplist != NULL);
	//将三个指针赋值
	pCur = *pplist;
	tmp = pCur->next;
	tmp2 = tmp->next;

	//原头节点先赋值为NULL
	pCur->next = NULL;

	while (tmp2 != NULL)
	{
		//改变指向
		tmp->next = pCur;

		//3个指针后移
		pCur = tmp;
		tmp = tmp2;
		tmp2 = tmp2->next;
	}

	//循环完毕最后一步的处理
	*pplist = tmp;
	tmp->next = pCur;
}

题目十六

题目十六：替换删除法、替换插入法

这两个方法也是链表操作中比较常见的方法，但是注意是非尾节点才可以使用替换删除法，替换插入法任何节点均可用！先上代码：

//删除一个无头单链表的非尾节点 
void EraseNotTail(pNode pos)
{
	pNode pCur = NULL;
	assert(pos != NULL);
	pCur = pos->next->next;
	pos->data = pos->next->data;
	free(pos->next);
	pos->next = pCur;
}

其实就是本来应该删除pos位置的节点，但是为了方便操作我们只能删除pos后面的节点，于是我们先把pos的next的next节点的位置存储起来，然后将pos的next节点的数据存到pos节点上，接着删除pos的next节点即可：

同样的道理，我们看看替换插入法：

//在无头单链表的一个节点前插入一个节点 
void InsertNode(pNode pos, DataType data)
{
	pNode pCur = NULL;
	pNode newNode = NULL;
	assert(pos != NULL);

	newNode = BuyNode(pos->data);
	if (newNode == NULL)
	{
		printf("空间不足\n");
		return;
	}
	pCur = pos->next;
	pos->next = newNode;
	pos->data = data;
	newNode->next = pCur;
}

同样的道理，本来我我们应该把新的节点插入到pos之前，但是由于这样是不好操作的，于是我们先把节点插入到了pos的后面，然后交换pos与新节点中的数据，这样便完成了所谓的“在pos之前插入”，优化方案：直接在产生新节点的时候就使用pos的data来构造节点，这样只需要将参数data赋值给pos的data即可！

题目十七

问题十七：逆序打印链表

普通的方式逆序打印链表此方法的思路就是使用两个指针，一个指针tail负责指向上一次刚刚被打印的元素，这样每次pCur指针每次都以tail指针标记作为结束，这样直到tail指针指向头结点的时候就证明已经打印完成了。看看下面这个小电影就能很容易的明白：

//1. 逆序打印单向链表 
void PrintTailToHead(pList plist)
{
	pNode pCur = NULL;
	pNode tail = NULL;
	assert(plist != NULL);

	pCur = plist;
	while (tail != plist)
	{
		while (pCur->next != tail)
		{
			pCur = pCur->next;
		}
		printf("%d ", pCur->data);
		tail = pCur;
		pCur = plist;
	}
}

递归的方式逆序打印链表

递归往往可以将复杂问题简单化，这里的极限条件是传入的参数不为空，那么直到将链表末尾的【NULL】传入才会直接返回，这样的话层层递归打印出的便是倒序的输出：

//递归的方式打印
void PrintTailToHead_R(pList plist)
{
	if (plist == NULL)
		return;
	PrintTailToHead_R(plist->next);
	printf("%d ",plist->data);
}