MS100(7)-编程判断两链表是否相交

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

问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?

1.首先假定链表不带环
那么，我们只要判断俩个链表的尾指针是否相等。
相等，则链表相交；否则，链表不相交。
2.如果链表带环，
那判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
如果在，则相交，如果不在，则不相交。

所以，事实上，这个问题就转化成了：
1.先判断带不带环
2.如果都不带环，就判断尾节点是否相等
3.如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
如果在，则相交，如果不在，则不相交。

//用两个指针，一个指针步长为1，一个指针步长为2，判断链表是否有环
bool check(const node* head)
{
    if(head==NULL)
      return false;
    node *low=head, *fast=head->next;
    while(fast!=NULL && fast->next!=NULL)
    {
        low=low->next;
        fast=fast->next->next;
        if(low==fast) return true;
    }
    return false;
}

//如果链表可能有环，则如何判断两个链表是否相交
//思路：链表1 步长为1，链表2步长为2 ，如果有环且相交则肯定相遇，否则不相交
list1 head: p1
list2 head: p2
while( p1 != p2 && p1 != NULL && p2 != NULL )
[b]//但当链表有环但不相交时，此处是死循环。![/b]
{
      p1 = p1->next;
      if ( p2->next )
         p2 = p2->next->next;
      else
         p2 = p2->next;
}
if ( p1 == p2 && p1 && p2)
   //相交
else
  //不相交
所以，判断带环的链表，相不相交，只能这样：
如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
如果在，则相交，如果不在，则不相交。

代码有空补上