本文共 3252 字，大约阅读时间需要 10 分钟。

题目：给定两个单链表的头节点head1和head2，如何判断两个链表是否相交？相交的话返回true，不想交的话返回false。给定两个链表的头结点head1和head2(注意，另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。

思路：题目要求就是简单的判断是否相交，更加通用的情况是判断有没有相交，如果相交返回第一个相交结点，如果不相交返回null。这道题目是前面两道题目的综合，由于不明确链表里面是否有环，而有环和没环情况下找出第一个相交结点是不同的，因此要分情况来考虑

①特殊输入，head1、head2有一个为null，不相交，交点为null；

②判断head1，head2是否有环—LB9，将这个处理过程提取为一个单独的函数

(1)设置两个指针pfast，pslow进行遍历，如果有环，记录返回入环的第一个结点(即如果pfast.next==null时返回无环，否则求得交点meetingNode，再返回入环结点)；

③根据有没有环分别处理

(1)如果链表1，链表2都没环，就是比较两个无环单链表是否相交并返回第一个交点的问题；（LB10）

(2)如果一个链表有环而另一个链表无环说明必定没有交点；

(3)如果链表1，链表2都有环，就是判断两个有环链表是否相交，如果相交返回第一个交点，如果不相交返回null；（LB11）

import java.util.*;public class ChkIntersection {        //为了代码复用，设置一个标志位，用于表示当参数为null时的情形    //ListNode mark=new new ListNode(0);    public boolean chkInter(ListNode head1, ListNode head2, int adjust0, int adjust1) {        //由于题目仅仅要求判断是否相交，但是采用更加通用的方法返回第一个相交的结点        ListNode returnFirstIntersectionNode=this.returnFirstIntersectionNode(head1,head2,adjust0,adjust1);        return returnFirstIntersectionNode==null ? false:true;     }        //给定两个链表head1，head2，如果相交，返回相交的第一个结点，否则返回null    public ListNode returnFirstIntersectionNode(ListNode head1, ListNode head2, int adjust0, int adjust1){        //特殊输入判断        if(head1==null||head2==null) return null;                //判断链表是否有环，如果有环返回第一个入环结点        ListNode entryNodeOfLoop1=this.entryNodeOfLoop(head1);        ListNode entryNodeOfLoop2=this.entryNodeOfLoop(head2);                //一个链表有环，一个没有环则必定不会相交        if(entryNodeOfLoop1==null&&entryNodeOfLoop2!=null) return null;        if(entryNodeOfLoop1!=null&&entryNodeOfLoop2==null) return null;                ListNode intersectionNode=null;                if(entryNodeOfLoop1!=null&&entryNodeOfLoop2!=null){        //此时，即两个链表都有环，且已经得到入环结点，即寻找两个有环链表的相交结点，调用方法intersectionNodeWithLoop()            intersectionNode=this.intersectionNodeWithLoop(head1,entryNodeOfLoop1,head2,entryNodeOfLoop2);        }else{            //如果两个链表都没有环就是寻找两个无环链表的相交结点的问题，调用方法intersectionNodeWithoutLoop()            intersectionNode=this.intersectionNodeWithoutLoop(head1,head2,null);        }        return intersectionNode;    }        //已知head！=null判断输入的链表是否有环，如果有环则返回环的第一个结点    public ListNode entryNodeOfLoop(ListNode head){        //如果只有一个结点则无环        if(head.next==null) return null;        //定义两个指针        ListNode pfast=head;        ListNode pslow=head;        pslow=pslow.next;        pfast=pfast.next.next;        while(pslow!=pfast){            //如果链表有尽头那么一定无环            if(pfast==null||pfast.next==null) return null;            pslow=pslow.next;            pfast=pfast.next.next;            }        //此时说明一定有环，记录pfast和pslow在环中的交点        ListNode meetingNode=pslow;        //得到入环结点        ListNode p=head;        while(p!=pslow){            p=p.next;            pslow=pslow.next;        }        return p;}//已知两个无环链表head1，head2，判断是否相交，若是返回第一个相交结点，否则返回null,为了代码复用，扩展为在head到tailHead之间找相交结点    public ListNode intersectionNodeWithoutLoop(ListNode head1,ListNode head2,ListNode tailNode){        //已知head1，head2不为空,即Y字形结构的比较，先得到链表的长度，为了代码复用，此时是求从head到tailHead结点的长度        int length1=listLength(head1,tailNode);        int length2=listLength(head2,tailNode);        ListNode longList=null;        ListNode shortList=null;        int diff=0;        if(length1

转载地址：http://xvzin.baihongyu.com/