C语言—链表面试题之带环问题的总结

布满荆棘的人生 2022-07-10 04:16 136阅读 0赞

# 链表带环问题 #

————————————————————————————

昨天在网上看到一个挺有趣的东西，链表带环问题，感觉很烧脑，但是可以锻炼我们的思想，我就闲来无事写一个博客总结

一下。所谓链表带环其实也就是让他最后一个结点的next成员指向自己第一个元素的，好开始！首先我们创建一个带环的链

表。这个自己写一个链表的后插函数，然后找到最后一个成员的next成员的地址，将它的内容改为你的头结点的地址，这样

的一个环就成功了。

pList plist = NULL;
    	pNode cur = plist;
    	PushBack(&plist, 1);
    	PushBack(&plist, 2);
    	PushBack(&plist, 3);
    	PushBack(&plist, 4);
    	PushBack(&plist, 5);
    	PushBack(&plist, 6);
    	PushBack(&plist, 7);
    	PushBack(&plist, 8);
    	cur = plist;
    	while (cur->next)
    	{
    		cur = cur->next;
    	}
    	cur ->next= plist;

pList plist2 = NULL;
    	PushBack(&plist2, 1);
    	PushBack(&plist2, 2);
    	PushBack(&plist2, 3);
    	PushBack(&plist2, 4);
    	PushBack(&plist2, 5);
    
    
    
    void PushBack(pList* pplist, DataType d)
    {
    	pNode cur = *pplist;
    	assert(pplist != NULL);
    	if (NULL == *pplist)
    	{
    		pNode newnode = buy(d);
    		*pplist = newnode;
    		return;
    	}
    	pNode newnode = buy(d);
    	while (cur->next)
    	{
    		cur = cur->next;
    	}
    	cur->next = newnode;
    	return;
    }

这是我创建出的两个链表，pushBack是我自己写的一个后插节点函数，因为环状的链表无法打印他们的样子我画图显示一下.

![20170712161957807][]

现在我们思考一个问题，如何解决一个链表是否带环呢？？  
  
第一种思路，也是我犯过的错误，就是思考着，环状的链表没有最后一个结点，但是直链表有啊，他的最有一个节点的next

成员为NULL判断这个就可以了，但是这里不可以，因为如果它真的是环状链表判断条件就不会成立，那么就是一个死循环程

序会崩溃掉。  
  
第二种思路，这样的方法很值得我们学习，用一个快慢指针，快指针，具体实现我画个图来看

![20170712162000964][]

代码实现:

pNode checkCylen(pList* pplist)
    {
    	pNode fast = *pplist;
    	pNode slow = *pplist;
    	assert(pplist);
    	while (fast && fast->next)
    	{
    		fast = fast->next->next;
    		slow = slow->next;
    		if (fast == slow)
    		{
    		printf("yes\n");
    		return slow;
    		}
    	}
    	printf("no\n");
    	return NULL;
    }
    int GetcircleLength(pNode meet)
    {
    	pNode cur = meet;
    	int count = 0;
    	while (1)
    	{
    		cur = cur->next;
    		count++;
    		if (cur == meet)
    		{
    			return count;
    		}
    	}
    }

第二个问题，如果它带环，你能否求出他的长度？上面知道的条件到这里都是我们知道的条件，长度怎么想呢？ 我们知道

我们只需要在环里的一个结点位置，就可以通过遍历知道找到这个结点地址并求出长度了。上面我们知道一个快慢指针相交

的节点，所以长度很容易啊。

代码实现:

int GetcircleLength(pNode meet)
    {
    	pNode cur = meet;
    	int count = 0;
    	while (1)
    	{
    		cur = cur->next;
    		count++;
    		if (cur == meet)
    		{
    			return count;
    		}
    	}
    }

这里的pNode meet就是上面那个函数返回回来的slow。  
  
接下来是第三个问题,找到入口点位置.

![20170712162004720][]

看到这个问题我的内心是拒绝的，真的，完全没有思路........  
  
这个问题是真的有难度，我最后查了查还是找到了答案.

![20170712162008222][]

代码实现:

pNode GetCycleEntryNode(pList plist, pNode meetNode)
    {
    	pNode cur = meetNode;
    	pNode cur2 = plist;
    	//前提它已经是一个环状链表
    	//plist和meetNode分别是链表的头结点位置和快慢指针相遇点
    	if (plist == NULL)
    	{
    		return NULL;
    	}
    	if (meetNode == NULL)
    	{
    		return NULL;
    	}
    	while (1)
    	{
    		if (cur == cur2)
    		{
    			return cur;
    		}
    		cur = cur->next;
    		cur2 = cur2->next;
    	}
    
    }

链表相交问题！！现在有一个问题，它让你求出2个链表是否相交若相交求出交点(有可能是直链表 有可能是带环链表)  
  
  
现在链表带环的大部分问题解决了，接下来你如何判断他们是否相交。 对就是判断两个链表是否相交。  
  
  
首先我们应该先知道，这里相交的所有情况。

![20170712162014130][]

第一种情况两个直链表，这个判断条件很容易就是观察他们的最后一个结点，是否一样，若是一样的那么他们一定相交。  
  
  
第二种情况 一个直链表 一个环状链表，记住这两个不可能！！ 他们不可能。因为呢，若是你两个相交你们一定都是环状

链表，或者他们都是直链表，不可能是一个直链表，一个环状链表。

第三种情况也就是两个环状链表相交，这个里面又分为2种小情况，相交但入口点不同，相交入口点相同  
  
  
  
  
代码实现

Node* checkCrossL(Linklist l2) //两个直链表的交点
    	{
    		Node* tmp = l2.end();
    		Node* cur = _head;
    		assert(tmp);
    		l2.end()->_next = _head;
    		return GetCycleEntryNode();
    	}
    
    	Node* checkCrossC(Linklist l2)//环状链表的交点
    	{
    		Node* cur1 = GetCycleEntryNode();
    		Node* cur2 = l2.GetCycleEntryNode();
    		if (cur1 == cur2)
    		{
    			cur2->_next = l2.begin();
    			return GetCycleEntryNode();
    		}
    		else
    		{
    			return cur1;
    		}
    	}
    
    	Node* checkCross(Linklist& l2)
    	{
    		if (checkCylen() == false && l2.checkCylen())//一个直链表 一个环状链表
    			return false;
    		if (checkCylen() && l2.checkCylen() == false)//一个直链表 一个环状链表
    			return false;
    		if (checkCylen() == false && l2.checkCylen() == false)//两个直链表
    		{
    			Node* cur1 = _head;
    			Node* cur2 = l2._head;
    			while (cur1->_next)
    			{
    				cur1 = cur1->_next;
    			}
    			while (cur2->_next)
    			{
    				cur2 = cur2->_next;
    			}
    			if (cur1 == cur2)
    			{
    				return checkCrossL(l2);
    			}
    			return 0;
    		}
    
    		if (checkCylen() && l2.checkCylen())//两个环状链表
    		{
    			Node* cur1 = GetCycleEntryNode();
    			Node* cur2 = l2.GetCycleEntryNode();
    
    			if (cur1 != cur2) //入口点不同
    			{
    				while (cur1->_next != cur1)
    				{
    					if (cur1 == cur2)
    						return checkCrossC(l2);
    					cur1 = cur1->_next;
    				}
    				return false;
    			}
    
    			if (cur1 == cur2) //入口点相同
    			{
    				return checkCrossC(l2);
    			}
    		}
    		return false;
    	}

这里运用到的一个核心思想就是没有一个环链表我创建一个环状链表，具体应用参见两个单链表相交求交点，当你创建出

一个环状 链表时交点就是我们 需要的入口点，可能又会有人说到你改变了链表的结构，这样会影响后面的使用，这些都不

用担心，我们所有 的操作都在函数当中进行，运用的也是局 部变量并不会对实际的链表造成改变，这些被改变的链表会随

函数结束而销毁.

![20170712162020221][]

最后一个问题，删除直链表中倒数第K个节点?

代码实现:

删除倒数第K个节点.

pNode DelKNode(pList *pplist, int k)
    {
    	pNode fast = *pplist;
    	pNode slow = *pplist;
    	pNode del = NULL;
    	assert(pplist);
    	if (*pplist == NULL)
    	{
    		printf("此链表为空\n");
    	}
    	while (fast->next)
    	{
    		--k;
    		if (k <= 0)
    		{
    			slow = slow->next;
    		}
    		fast = fast->next;
    	}
    	del = slow->next;
    	slow->data = slow->next->data;
    	slow->next = slow->next->next;
    	free(del);
    	return NULL;
    }

这个代码实现起来很简单，现在你绝对会理解，我就不写了。大概这么多，这些问题的大致方法，已经全部写完了，自我

感觉良好。 哈哈，这就是我这两天学到的知识，并且把它写出来还觉得不错诶。

[20170712161957807]: /images/20220709/a3dbb6cc0aa74ba19b522a8feaab8b38.png
[20170712162000964]: /images/20220709/f6fde4eedef1434e845a9bfa7a407c9d.png
[20170712162004720]: /images/20220709/85604a6d0ed64f49b6511ea8e1ec8afa.png
[20170712162008222]: /images/20220709/eef74a56635d4824b92a09258801532b.png
[20170712162014130]: /images/20220709/7aa9e7106ecc462580b9e2f0044f3569.png
[20170712162020221]: /images/20220709/319b7acab930402d947050db55720731.png