法1、對鏈表1中的每個節(jié)點p1，判斷鏈表2中是否有一個節(jié)點p2指向p1
loop:p1從head1到最后一個節(jié)點
loop:p2從head2到最后一個節(jié)點
   if(p2是否指向p1)
    相交
    break
時間復(fù)雜度：O(list1.length * list2.length)
空間復(fù)雜度：O(1)
法2、使用hash表
loop：p1從head1到最后一個節(jié)點
把p1放入hash表table中
loop:p2從head2到最后一個節(jié)點
if(p2在hash表中)
   相交
時間復(fù)雜度:O(list1.length + list2.length)
空間復(fù)雜度：O(list1.length)
法3、將其中一個鏈表首尾相連，檢測另一個鏈表是否存在環(huán)，如果存在，則兩個鏈表相交，而檢測出來的依賴環(huán)入口點即為相交的第一個點。程序描述如下：
找到list1的最后一個節(jié)點tail1
tail1->next=head1
判斷head2是否存在環(huán)
tail1->next=NULL; //恢復(fù)tail1

法4、如果兩個鏈表相交，那么兩個鏈表從相交點到鏈表結(jié)束都是相同的節(jié)點。可以先分別遍歷找出兩個鏈表的尾節(jié)點，如果連個尾節(jié)點相同，則兩個鏈表相交。程序描述如下：
//找到list1的最后一個節(jié)點p1
p1=head1
while(p1->next不是NULL)
p1=p1->next
找出list2的最后一個節(jié)點p2
if(p1==p2)
相交
else
不相交
時間復(fù)雜度:O(list1.length + list2.length)
空間復(fù)雜度：O(1)

擴展問題4、如果兩個鏈表相交，找出相交的第一個節(jié)點？
在判斷相交的過程中要分別遍歷兩個鏈表，同時記下各自的長度。然后再遍歷一次：長鏈表節(jié)點先從頭節(jié)點出發(fā)前進(lengthMax-lenghMin)步，之后兩個鏈表同時前進，每次一步，相遇的第一個節(jié)點即為兩個鏈表相交的第一個節(jié)點。程序描述如下：
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)
   pLen++; 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