算法6— 判断两个链表是否相交

本文主要是介绍算法6— 判断两个链表是否相交，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题：

给出两个单向链表的头指针，比如h1、h2，判断链表是否相交，如果不相交返回NULL；如果相交，返回指向第一个相交节点的指针。时间复杂度控制在O(n)。

分析：

如果两单向链表相交的话，一定是Y型相交，不可能出现X型，弄清楚这点后接下来的工作就是：
（1）先找到h1，h2的最后一个节点L1和L2，同时记录节点数量a，b；（这里假设 a > b）
（2）判断最后一个节点是否相同；
如果不相同则没相交；
如果相同，则从第一个节点 (短链表) 和第 |a-b|+1个节点（长链表）开始比较（这样，两个链表的指针到相交点的距离是一样的），看是否相等，不相等就寻找下一个节点直到找到交叉点。

代码如下：

[java]  view plain copy  
 class Node {  
     char value;  
     Node next;  
 }  

[java]  view plain copy  
 Node intersect(Node h1, Node h2) {  
     // l1 and l2 refer to the last nodes in the two lists.  
     // a and b refer to the length of the lists.  
     Node l1 = h1;  
     int a = 1;  
       
     Node l2 = h2;  
     int b = 1;  
       
     while (l1.next != null) {  
         l1 = l1.next;  
         a++;  
     }  
       
     while (l2.next != null) {  
         l2 = l2.next;  
         b++;  
     }   
     // no intersection  
     if (l1 != l2) {  
         return null;  
     }   
     //move the pointer of the longer list.  
     for (int i = 0; i < Math.abs(a - b); i++) {  
         if (a > b) {           
             h1 = h1.next;  
         } else {  
             h2 = h2.next;  
         }     
     }  
       
     while (h1 != h2) {  
         h1 = h1.next;  
         h2 = h2.next;  
     }  
       
     return h1;  
 }   