#include <iostream> #include <assert.h> using namespace std; struct NODE { int value; NODE* next; }; /* 如何判断两个链表是否相交,在解决这个问题之前我们可以先做下简化, 即:我们假设两个链表均不带环。《编程之美》给出了这个问题的解决方案: 方案一、如果两个无环单链表相交于某一个节点,那么这个节点之后的所有节 点为两个链表所共有。通过比较两个链表的最后一个指针是否相同即可得到判断 结果。 */ bool IsIntersect1(NODE* head1,NODE* head2) { assert(head1&&head2); NODE* p1=head1; while(p1->next) p1=p1->next; //list1的最后一个非空节点 NODE* p2=head2; while(p2->next) p2=p2->next; //list2的最后一个非空节点 return p1==p2; } /* 方案二、将第二个链表接到第一个链表后面,如果得到的链表有环,则说明这两个 链表相交,否则不相交。 */ bool IsIntersect2(NODE* head1,NODE* head2) { assert(head1&&head2); NODE* p=head1; while(p->next) p=p->next; //list1的最后一个非空节点 p->next=head2; //list2链接到list1的后面 NODE* q=head2->next; while(q!=head2&&q!=NULL) //从head2开始往下遍历,若回到head2则相交 q=q->next; p->next=NULL; //将list2从list1后面断开 if(q==NULL) return false; else return true; } /* 我们把问题变复杂一点,在链表中可能存在环的情况下如何判断两个链表是否 相交? 条件是可能存在环,说明有以下三种情况: (1)这两个链表都无环,这种情况下的判断上面已经说过了; (2)一个链表有环一个链表无环,这种情况下两个链表一定不相交; (3)两个链表都有环。 要完整的解决这个问题我们可以对三种情况分别处理具体可参考
here :http://blog.163.com/bbluesnow@126/blog/static/27784545201251051156817/