【数据结构】寻找2个单链表相同的值

在关于基础单链表的面试题中，有一道这样的面试题：

打印输出2个链表中的相同节点。

比如2个这样的链表。

你们也许会说，这个不是灰常灰常简单么。一个链表的一个值与另外一个链表的所有值比较，然后相同就输出它不就行了么。但是这样遍历的复杂度就高了，如果面试官会要求你只能够遍历这个链表一次的情况下去怎么做呢？

大家仔细思考一下：

1.2个链表2个指针，

2.然后当其中一个指针的值大的时候它就往后移。

3.相等2个输出当前节点，然后2个指针同时往后移动这不就好了么=。=

这个思路比较简单，我直接给出代码

voidFindEqualData(PLinkNodeoneHead,PLinkNodetwoHead)
{
	//升序降序判断值，升序为0降序为1；
	intsortFlag=0;
	assert(NULL!=oneHead&&NULL!=twoHead);
	printf("相同的数据是:");
	if(oneHead->_data>oneHead->_next->_data)
	{
		sortFlag=1;
	}
	while(oneHead!=NULL&&twoHead!=NULL)
	{
		if(oneHead->_data>twoHead->_data)
		{
			if(1==sortFlag)
			{
				oneHead=oneHead->_next;
			}
			else
			{
				twoHead=twoHead->_next;
		
			}
		}
		elseif(oneHead->_data==twoHead->_data)
		{
			printf("%d",oneHead->_data);
			twoHead=twoHead->_next;
			oneHead=oneHead->_next;
		}
		elseif(oneHead->_data<twoHead->_data)
		{
			if(1==sortFlag)
			{
				twoHead=twoHead->_next;
			}
			else
			{
				oneHead=oneHead->_next;
		
			}
		}
	}
}

在这个查找函数中，我增加了一个Flag值得判断，来由此判断这2个是升序链表还是降序列表，在面试的时候考虑一个问题必须要问清楚，在思考这个问题就需要跟面试官或者自己加上备注，要求，因为当一个是降序一个是升序的时候，之遍历一遍是不可能输出的。

只有当他们2个链表同时为升序链表或者是降序链表的时候才能够一次遍历完成相同值得输出。

就这样=。=

愿诸君与我一起进步。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!