网站建设资讯

NEWS

网站建设资讯

单链表的一些经典面试题-创新互联

今天在一本试题书上看到一些特别好的单链表面试题,大家都知道单链表容易在头节点处进行删除,在尾节点处进行插入,下面我们就来讨论一下这些面试题:

成都创新互联坚信:善待客户,将会成为终身客户。我们能坚持多年,是因为我们一直可值得信赖。我们从不忽悠初访客户,我们用心做好本职工作,不忘初心,方得始终。10余年网站建设经验成都创新互联是成都老牌网站营销服务商,为您提供网站建设、成都网站设计、网站设计、成都h5网站建设、网站制作、成都品牌网站建设小程序开发服务,给众多知名企业提供过好品质的建站服务。

 (一)删除一个非尾节点

 题目要求的是要删除一个不是尾节点的节点,要删除一个节点我们首先得知道是那个链表,是哪个节点节点,找到并且删除它。所以我们设计的函数是这样的:

void DelNotTailNode(SListNode* pos)
{
	assert(pos);
	SListNode* del = pos->next;
	pos->data = del->data;
	pos->next = del->next;
	free(del);
	del = NULL;
}

 其实实现起来也很简单,主要思想是删除pos位置的下一个节点,因为单链表只可以找到当前结点的下一个节点。

单链表的一些经典面试题

(二)找到单链表的中间节点:

题目要求只遍历一次就找到这个中间节点,可见按照我们的常规思路,先遍历一遍计数节点的总个数,然后二遍遍历直接找到节点是不行的。这就用到了单链表一个重要的概念——快慢指针。定义两个指针slow和fast,slow指针每次往后走一个节点位置,fast指针每次往后走俩个节点位置,当fast指针走到尾节点时,slow指针刚刚好走到中间节点位置;

SListNode* FindMidNode(SListNode* pHead)//pHead是链表的头节点
{
	SListNode* fast = pHead;
	SListNode* slow = pHead;
	while (fast->next)
	{
		slow = slow->next;
		fast = fast->next;
		if (fast->next)
		{
			fast = fast->next;
		}
		else
		{
			break;
		}
	}
	return slow;
}

利用快慢指针可以解决很多类似的问题,比如找到单链表的第N个节点,或者判断链表是否带环等等,下面会有列子。

(三)判断一个链表是否带环,若带返回环的入口点(较难)

上面已经说过,通过快慢指针可以找到单链表中的任何节点,这也是通过验证的。那么原理上也可以判断链表是否带环:

 如果带环,快慢指针一定会在某个节点处相遇。(fast一直在环里转,总有一个时刻,slow追上fast,相遇)

SListNode* WhetherRing(SListNode* pHead)//判断是否带环,若带,返回相遇节点
{
	if (pHead == NULL||pHead->next == NULL)
		return NULL;
	SListNode* fast = pHead;
	SListNode* slow = pHead;
	while (fast)
	{
		slow = slow->next;
		fast = fast->next;
		if (fast)
		{
			fast = fast->next;
		}
		else
		{
			return NULL;//没有环
		}
		if (fast == slow)
		{
			return slow;//有环
		}
	}
	return NULL;
}

单链表的一些经典面试题

  如果链表带环的话,我们就可以求出相遇的节点。然后从相遇节点处断开带环链表,一个指针从链表投节点处开始往后遍历,一个指针从断开处往后遍历,相遇节点处就是环的入口点

单链表的一些经典面试题

SListNode* GetEnterNode(SListNode*  pHead)//找到链表环入口节点在哪(重点)
{
	SListNode* start = pHead;
	SListNode* tmp = WhetherRing(pHead);
	while (start != tmp)
	{
		start = start->next;
		tmp = tmp->next;
	}
	return start;
}

 这就是单链表的一些面试经典题,我通过理解后和大家一起分享,希望对大家有些许帮助。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


网站标题:单链表的一些经典面试题-创新互联
当前网址:http://njwzjz.com/article/djggjg.html