编程之美上的一道题。

给出两个单向链表的头指针，比如h1和h2，判断这两个链表是否相交。先假设链表不带环。

首先对于“链表相交”这个概念，要澄清一下，不是单点相交，而是如下这种：

其实也很好理解，相交在平面几何里面的概念是点重合。那么对于链表中某个结点重合，必然next指针也是一样的，于是就是上面这个样子了。

思路：如上分析后就很简单了，如果相交，那么肯定从h1找到尾部(NULL的前一个)和好

找到的尾部是重合的。如果不重合，肯定不相交，是重要条件。

代码如下：

int ll_is_cross(struct Node* a, struct Node* b)
{
	if(a==NULL || b==NULL)
	{
		return -1;
	}
	while(a->next!=NULL)
	{
		a = a->next;
	}
	while(b->next!=NULL)
	{
		b = b->next;
	}
	if(a==b)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

其他支持代码如下：

#include <iostream>

struct Node
{
	struct Node* next;
	int data;
};

int ll_append(struct Node* & root, int data)
{
	if(root==NULL)
	{
		root = new Node();
		root->next = NULL;
		root->data = data;
		return 0;
	}else
	{
		struct Node* ptr = root;
		while(ptr->next!=NULL)
		{
			ptr = ptr->next;
		}
		// Append to tail
		ptr->next = new Node();
		if(!ptr->next)
		{
			return -1;
		}
		ptr->next->data = data;
		ptr->next->next = NULL;
		return 0;
	}
}

// Merge b to a's tail
int ll_merge(struct Node* a, struct Node* b)
{
	if(a==NULL || b==NULL)
	{
		return -1;
	}
	while(a->next!=NULL)
	{
		a = a->next;
	}
	a->next = b;
}

void ll_print(struct Node* root)
{
	while(root!=NULL)
	{
		::std::cout << root->data << " ";
		root = root->next;
	}
	::std::cout << ::std::endl;
}

int main()
{
	struct Node* list1 = NULL;
	struct Node* list2 = NULL;
	struct Node* list3 = NULL;
	for(int i=1;i<=4;i++)
	{
		ll_append(list1, i);
	}
	for(int i=5;i<=8;i++)
	{
		ll_append(list2, i);
	}
	ll_append(list3, 1);
	ll_append(list3, 3);
	ll_merge(list1, list2);
	ll_merge(list3, list2);
	ll_print(list1);
	ll_print(list3);
	::std::cout << "list cross: " << ll_is_cross(list1, list2) << ::std::endl;
	return 0;
}

 如果现在要求把重复的部分打出来应该怎么做呢？

其实也不复杂，我们设A链表A和B的长度分别是是L(a)和L(b)，则让短的哪个链表走 |L(a) - L(b)| 步，然后开始比较两个指针，直到有相等的即可。

代码如下：

void ll_is_cross_and_print(struct Node* heada, struct Node* headb)
{
	struct Node* a = heada; 
	struct Node* b = headb; 
	if(a==NULL || b==NULL)
	{
		return ;
	}
	int lena = 0;
	while(a->next!=NULL)
	{
		a = a->next;
		lena++;
	}
	int lenb = 0;
	while(b->next!=NULL)
	{
		b = b->next;
		lenb++;
	}
	if(a==b)
	{
		// cross, then would print cross part
		a = heada;
		b = headb;
		if(lena<lenb)
		{
			int i = 0;
			while(i<(lenb-lena))
			{
				b = b->next;
				i++;
			}
		}else 
		{
			int i = 0;
			while(i<(lena-lenb))
			{
				a = a->next;
				i++;
			}
		}
		::std::cout << a->data <<::std::endl;
		::std::cout << b->data <<::std::endl;
		while(a!=NULL && b!=NULL)
		{
			if(a==b)
			{
				::std::cout << "Cross part:";
				ll_print(a);
				break;
			}else
			{
				a = a->next;
				b = b->next;
			}
		}
		return ;
	}
	else
	{
		// no cross
		::std::cout << "No cross part;" << ::std::endl;
		return ;
	}
}