链表 | 如何判断两个单链表(无环)是否交叉

如何判断两个单链表（无环）是否交叉

单链表相交指的是两个链表存在完全重合的部分，如下图所示

在上图中，这两个链表相交于结点5，要求判断两个链表是否相交，如果相交，找出相交处的结点。

分析

Hash法

如上图所示，如果两个链表相交，那么它们一定会有公共的结点，由于结点的地址或引用可以作为结点的唯一标识，因此，可以通过判断两个链表中的结点是否有相同的地址或引用来判断链表是否相交。

具体可以采用如下方法实现：

首先遍历链表head1，把遍历到的所有结点的地址存放到HashSet中；

接着遍历链表head2，每遍历到一个结点，就判断这个结点的地址在HashSet中是否存在，如果存在，那么说明两个链表相交并且当前遍历到的结点就是它们的相交点，否则直到链表head2遍历结束，说明这两个单链表不相交。

算法性能分析

由于这种方法需要分别遍历两个链表，因此，算法的时间复杂度为O（n1+n2）。

其中，n1与n2分别为两个链表的长度。

此外，由于需要申请额外的存储空间来存储链表head1中结点的地址，因此，算法的空间复杂度为O（n1）。

首尾相接法

主要思路：将这两个链表首尾相连（如把链表head1尾结点链接到head2的头指针），然后检测这个链表是否存在环，如果存在，则两个链表相交，而环入口结点即为相交的结点，如下图所示。

尾结点法

主要思路：如果两个链表相交，那么两个链表从相交点到链表结束都是相同的结点，必然是Y字形（如上图所示）。所以，判断两个链表的最后一个结点是不是相同即可。即先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交，这时记下两个链表的长度n1、n2，再遍历一次，长链表结点先出发前进|n1-n2|步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

代码实现

/**
* 判断两个单链表（无环）是否交叉
*
* @author Java后端技术栈 tian
*/
public class CommonLoopNode {
   //找出交叉点
   public static Node findOverlap(Node head1, Nodehead2) {
       if (head1 == null || head1.next == null) {
           return null;
      }
       if (head2 == null || head2.next == null) {
           return null;
      }
       Node temp1 = head1.next;
       Node temp2 = head2.next;

       int n1 = 0, n2 = 0;
       //遍历head1,找到尾节点,同时记录head1的长度
       while (temp1.next != null) {
           temp1 = temp1.next;
           ++n1;
      }
       //遍历head2,找到尾节点,同时记录head2的长度
       while (temp2.next != null) {
           temp2 = temp2.next;
           ++n2;
      }
       //head1与head2有相同的尾节点
       if (temp1 == temp2) {
           //长链表的先走|n1-n2|
           if (n1 > n2) {
               while (n1 - n2 > 0) {
                   head1 = head1.next;
                   --n1;
              }
          }
           if (n2 > n1) {
               while (n2 - n1 > 0) {
                   head2 = head2.next;
                   --n2;
              }
          }
           while (head1 != head2) {
               head1 = head1.next;
               head2 = head2.next;
          }
           return head1;
      } else {
           //head1和head2没有相同的尾节点
           return null;
      }
  }

   public static void main(String[] args) {
       int i = -1;
       Node head1 = new Node();
       head1.next = null;

       Node head2 = new Node();
       head2.next = null;

       Node temp;
       Node cur = head1;
       Node p = null;

       //构造第一个head1
       for (; i < 8; i++) {
           temp = new Node();
           temp.data = i;
           temp.next = null;
           cur.next = temp;
           cur = temp;
           if (i == 5) {
               p = temp;
          }
      }

       cur = head2;
       //构造第一个head2
       for (i = 1; i < 5; i++) {
           temp = new Node();
           temp.data = i;
           temp.next = null;
           cur.next = temp;
           cur = temp;
      }

       //AA（关键点）使两个链表相较于节点5
       cur.next = p;

       print(head1, head2);

       Node interNode = findOverlap(head1, head2);
       if (interNode == null) {
           System.out.println("两个链表不存在相交点");
      } else {
           System.out.println("两个链表相较于节点：" +interNode.data);
      }
  }
   //打印
   private static void print(Node head1, Node head2) {
       System.out.println();
       Node printNoe = head1;
       while (printNoe.next != null) {
           printNoe = printNoe.next;
           System.out.print(printNoe.data + " ");
      }
       printNoe = head2;
       System.out.println();
       while (printNoe.next != null) {
           printNoe = printNoe.next;
           System.out.print(printNoe.data + " ");
      }
       System.out.println();
  }
}

运行结果

在上述代码中，由于构造的两个单链表相交于结点5，因此，输出结果中它们的相交结点为5。

如果还存在疑惑不清楚的，请结合代码和图一起看。

算法性能分析

假设这两个链表长度分别为n1、n2，重叠的结点的个数为L（0＜L＜min（n1,n2）），则总共对链表进行遍历的次数为n1+n2+L+n1-L+n2-L=2（n1+n2）-L。

因此，算法的时间复杂度为O（n1+n2）。

由于这种方法只使用了常数个额外指针变量，因此，空间复杂度为O（1）。

引申

如果单链表有环，如何判断两个链表是否相交。

1）如果一个单链表有环，另外一个没有环，那么它们肯定不相交。

2）如果两个单链表都有环并且相交，那么这两个链表一定共享这个环。