美文网首页
单链表相交判断

单链表相交判断

作者: IT_Matters | 来源:发表于2016-07-06 11:11 被阅读15次

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

思路

结合之前有环链表相交无环链表相交 的思考, 我们需要先对链表的类型进行判断. 如果两个都是同一类型的链表,则重用之前的代码进行判断即可,如果一个是有环,一个是无环的链表,则它们不可能相交.

public class ChkIntersection {
    public boolean chkInter(ListNode head1, ListNode head2, int adjust0, int adjust1) {
        if(head1==null||head2==null)return false;
        ListNode entry1=findCycleEntry(head1);
        ListNode entry2=findCycleEntry(head2);
        
        //两个无环链表
        if(entry1==null||entry2==null){
           return chkIntersect(head1,head2);
        }
        //两个有环链表
        else if(entry1!=null&&entry2!=null){
            if(entry1==entry2){
               return true;
            }
             else{
              ListNode backup=entry1;
              do{
                entry1=entry1.next;
              }while(entry1!=entry2&&entry1!=backup);
              return !(entry1==backup);
             }
        }
        //一个有环一个无环
        else return false;
    }
    
    //找到入环节点
    private ListNode findCycleEntry(ListNode head){
        if(head==null||head.next==null)return null;
        ListNode fast=head,slow=head;
        do{
            slow=slow.next;
            fast=fast.next.next;

        }while(slow!=fast&&fast.next!=null&&fast.next.next!=null);
        if(slow!=fast)return null;
        slow=head;
        while(slow!=fast){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }  

    //查找无环链表相交情况
    public boolean chkIntersect(ListNode headA, ListNode headB) {
        // write code here
        int lenA=getListLen(headA);
        int lenB=getListLen(headB);
        if(lenA==0||lenB==0)return false;

        if(lenA<lenB){
            headB=runKNode(headB,lenB-lenA);
        }
        else{
            headA=runKNode(headA,lenA-lenB);
        }
        while(headA!=null&&headA!=headB){
            headA=headA.next;
            headB=headB.next;
        }
        return headA==null?false:true;

    }
    
     private int getListLen(ListNode head){
        int len=0;
        while(head!=null){
            len++;
            head=head.next;
        }
        return len;
    }
    
    private ListNode runKNode(ListNode head,int len){
        for(int i=0;i<len;i++){
            head=head.next;
        }
        return head;
    }
}

相关文章

  • 单链表相交判断

    给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不想交的话返回fal...

  • 判断两个单链表是否相交及找到第一个交点

    题目:给两个单链表,如何判断两个单链表是否相交?若相交,则找出第一个相交的节点。这道题的思路和解法有很多,在这把这...

  • 单链表的就地逆置--java实现(含头节点和不包含头节点)

    前沿:链表是面试中经常问道的知识点,比如链表反转,就地反转,判断单链表是否相交,判断链表是否有环等都是常问的问题....

  • 有环单链表相交判断

    如何判断两个有环单链表是否相交?相交的话返回true,不想交的话返回false。如果两个链表长度分别为N和M,请做...

  • 有环单链表相交判断练习题

    题目 如何判断两个有环单链表是否相交?相交的话返回第一个相交的节点,不想交的话返回空。如果两个链表长度分别为N和M...

  • 关于求两个单链表相交的第一个节点的问题分析

    判断两个单链表是否相交以及相交的情况下求第一个相交节点,两个链表可以有环,也可以无环。因此我们可以从以下几个步骤分...

  • 链表相交的问题(java)

    判断两个无环链表是否相交首先我们要知道相交是什么概念两个链表相交.png现在大家都知道了,两个链表相交,则两个链表...

  • leetcode的题目160

    160. 相交链表 编写一个程序,找到两个单链表相交的起始节点。 例如,下面的两个链表: 在节点 c1 开始相交。...

  • 2019-01-25 Day 20

    1.#### 相交链表编写一个程序,找到两个单链表相交的起始节点。 如下面的两个链表: 在节点 c1 开始相交。 ...

  • 链表小题目

    如何判断两条单向链表是否相交,以及相交节点 同时遍历两个链表,求出长度差,然后长的链表走完 N次以后,短链表再开始...

网友评论

      本文标题:单链表相交判断

      本文链接:https://www.haomeiwen.com/subject/ukdkjttx.html