《微软面试题》判断2个单向链表的是否有交叉点 - Linux安全网 - Linux操作系统_Linux 命令_Linux教程

《微软面试题》判断2个单向链表的是否有交叉点

日期:2011-12-09 点击:161 来源: yynetsdk 分享至:

微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。

问题扩展：
1.如果链表可能有环列?

2.如果需要求出俩个链表相交的第一个节点列?

comNode.h

#pragma once

//check two single-list does have com node

template<typename T>
class ListNode
{
public:

	ListNode(T t)
	{
		data = t;
		next = NULL;
	}

	T data;
	ListNode * next;
protected:
private:
};

template<typename T>
class List
{
public:

	List()
	{
		cur = NULL;
	}

	ListNode<T> * cur;

	void pushback(ListNode<T> * node)
	{
		if (cur == NULL)
		{
			cur = node;
		}
		else
		{
			cur->next = node;

			cur = node;

			cur->next = NULL;
		}
	}

	ListNode<T> * GetEnd()
	{
		while(cur->next != NULL)
		{
			cur = cur->next;
		}

		return cur;
	}

protected:
private:
};

main.cpp

typedef ListNode<int> _listnode;
typedef List<int> _list;


int _tmain(int argc, _TCHAR* argv[])
{
	_list mylist,mylist2;

	for (int i=0;i<10;i++)
	{
		_listnode *p = new _listnode(i);

		mylist.pushback(p);

		if (i == 5)
		{
			mylist2.pushback(p);
		}
	}

	printf("end data=%d\n",mylist.GetEnd()->data);

	printf("end data=%d\n",mylist2.GetEnd()->data);

	if (mylist2.GetEnd() == mylist.GetEnd())
	{
		printf("same end node\n");
	}
	
	getchar();

	return 0;
}

问题可归结为，如有相同end节点，则有交叉点。

Tags：

分享至: