求循环和非循环单链表的交集问题是链表类型中最难的问题之一，我们一一听。1.题目描述给定两个可能有环也可能没有环的单向链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，则返回null要求：如果两个链表的长度之和为N，请时间复杂度达到O(N)，附加空间复杂度达到O(1)。2.思路解决思路分两步：（1）找到单向链表的入口点，如果没有循环则返回null（2）根据得到的链表入口点进行讨论1、找到单向链表的入口链接如果没有循环，则返回null(1)遍历单向链表，如果遍历的节点为null，则单向链表一定没有循环(2)否则，准备一个快速指针如果存在循环，则为慢指针。一开始，两个指针都从头节点开始，快指针一次走两个节点，慢指针一次走一个节点，直到两个指针相遇。此时快指针开始从头节点开始行走，一次一个节点；慢指针从交汇点继续往下走，仍然一次走一个节点，两个指针再次交汇时的节点就是入口节点。2.根据得到的链表的入口点，展开讨论(1)两个链表都是无环的。遍历其中一个链表，记录链表长度length1和最后一个节点end1；遍历另一个链表，记录链表长度length2和最后一个节点end2。如果end1和end2不相等，则两个链表一定不相交；否则计算length1和length2的差a，长链表先走一个结点，然后两个链表一个一个往下走。第一个相等的节点是第一个相交的节点。(2)一个有环，一个没有环。在这种情况下，两个链表不可能相交。（你可以试着在脑子里编出这样的结构，记住是单链表）（3）两个链表中都有三种环，每一种都有环但不相交；入口点相同；入口点有两个。1）它们有环但不相交2）入口点相同3）两个链表有两个入口点。两个链表的入口点相等：即入口点相同。它们都是无环的，相交过程相同，即求解时可以完全忽略后面的环。两个链表的入口节点不相等：是第一个赛跑还是第三个赛跑。此时从其中一个入口点开始，绕一圈。如果回到自己身边遇到第二个切入点，就是第三亚种，否则就是第一亚种。三、详细参考代码1、查找单向链表的入口/***查找单向链表的入口，没有循环则返回null**@authorJava与算法学习：星期一*/publicstaticNodegetLoopNode(Nodehead){if(head==null||head.next==null||head.next.next==null){returnnull;}//快速指针节点fast=head.next.next;//慢指针节点slow=head.next;while(fast!=slow){//如果某个快指针在走的过程中变空了，那么这个单链表一定是无环的if(fast.next==null||fast.next.next==null){returnnull;}}fast=fast.next.next;慢=慢.next;}//当快慢指针相遇时，快指针再次从头结点开始行走fastle=head;=fwhiad;slow){//这个时候就不用再判断为空了。如果能到这里，单向链表一定有环//这时候fast指针一个节点走一个节点fast=fast.next;//慢指针仍然是一次走一个节点slow=slow.next;}returnslow;}2.根据得到的链表的入口点，开始讨论(1)两个链表都是无环的/***现在我们知道两个链表都是无环的，找到它们的第一个相交节点**@authorJava和算法学习：周一*/publicstaticNodenoLoop(Nodehead1,Nodehead2){if(head1==null||head2==null){returnnull;}节点current1=head1;节点current2=head2；诠释n=0;//遍历一次链表得到长度和最后一个节点while(current1.next!=null){n++;当前1=当前1.下一个；}//得到链表的第二次遍历长度差，最后一个节点while(current2.next!=null){n--;current2=current2.next;}//如果两个链表的最后一个节点不相等，则它们一定不相交if(current1!=current2){returnnull;}//长链表的头节点给current1current1=n>0?头1：头2；//短列表的头节点给current2current2=current1==head1?head2:数学abn=head1;(n);//长链表首先遍历n个节点while(n!=0){n--;当前1=当前1.下一个；}//两个链表依次往下走，第一次相等的结点为第一个相交结点while(current1!=current2){current1=current1.next;current2=current2.next;}returncurrent1;}(3)两个链表都有环/***两个链表都有环*分三种情况，各有环但不相交；入口点相同；有两个入口点**@authorJava和算法学习：周一*/publicstaticNodebothLoop(Nodehead1,Nodeloop1,Nodehead2,Nodeloop2){Nodecurrent1=null;节点current2=空；如果(loop1==loOP2){current1=head1;当前2=头2；诠释n=0;//计算head1链表空间(Current1!=LOOP1)有多少个节点{n++;carent1。//计算两个链表节点个数之差。/短链表的头节点给current2current2=current1==head1?头2：头1；n=Math.abs(n);//长链表先到n个节点while(n!=0){next1=current;n--;}}返回当前1；}else{//如果两个链表的入口点不相等，则各自有环但不相交或者有两个入口点current1=loop1.next;//从其中一个切入点开始，遍历一圈，如果回到自己的时候遇到第二个切入点，则有两个切入点while(Current1!=Loop1){if(Current1==Loop2){//此时两个in-link节点是第一个交集节点，其中一个可以Returnloop1;}Current1=Current1.next;无效的;}}以上是核心详细参考代码。相信主要方法和测试方法都可以轻松写出来。当然，我想参考所有的代码。这里也是本文所有代码的Github地址：https://github.com/monday-pro...
