判断两个单链表是否相交

法1、对链表1中的每个节点p1，判断链表2中是否有一个节点p2指向p1
loop:p1从head1到最后一个节点
loop:p2从head2到最后一个节点
   if(p2是否指向p1)
    相交
    break
时间复杂度：O(list1.length * list2.length)
空间复杂度：O(1)
法2、使用hash表
loop：p1从head1到最后一个节点
把p1放入hash表table中
loop:p2从head2到最后一个节点
if(p2在hash表中)
   相交
时间复杂度:O(list1.length + list2.length)
空间复杂度：O(list1.length)
法3、将其中一个链表首尾相连，检测另一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口点即为相交的第一个点。程序描述如下：
找到list1的最后一个节点tail1
tail1->next=head1
判断head2是否存在环
tail1->next=NULL; //恢复tail1

法4、如果两个链表相交，那么两个链表从相交点到链表结束都是相同的节点。可以先分别遍历找出两个链表的尾节点，如果连个尾节点相同，则两个链表相交。程序描述如下：
//找到list1的最后一个节点p1
p1=head1
while(p1->next不是NULL)
p1=p1->next
找出list2的最后一个节点p2
if(p1==p2)
相交
else
不相交
时间复杂度:O(list1.length + list2.length)
空间复杂度：O(1)

扩展问题4、如果两个链表相交，找出相交的第一个节点？
在判断相交的过程中要分别遍历两个链表，同时记下各自的长度。然后再遍历一次：长链表节点先从头节点出发前进(lengthMax-lenghMin)步，之后两个链表同时前进，每次一步，相遇的第一个节点即为两个链表相交的第一个节点。程序描述如下：

Node *intersection(Node *head1, Node *head2)
if(!head1 || !head2)
   return NULL;
int len1 = 1;
int len2 = 1;
bool result = false;
//判断两个链表是否相交，同时记下各个链表的长度
Node *p = head1;
while(p->next)
   len1++; p=p->next
q=head2
while(q->next)
   len2++; q=q->next
result=(p==q)
if(result)
   int steps = abs(len1 – len2)
   Node *head = len1 > len2 ? head1 : head2;
   while(steps)
    head = head->next
    steps –-
   len1 > len2 ? p = head,q=head2 ? q = head,p=head1
   while(p!=q)
    p=p->next
    q=q->next
   return p
return NULL

 

转自http://www.cnblogs.com/lvpei/archive/2011/02/16/1956422.html