如何判斷兩個(gè)有環(huán)單鏈表是否相交？相交的話返回true，不想交的話返回false。如果兩個(gè)鏈表長度分別為N和M，請做到時(shí)間復(fù)雜度O(N+M)，額外空間復(fù)雜度O(1)。
給定兩個(gè)鏈表的頭結(jié)點(diǎn)head1和head2(注意，另外兩個(gè)參數(shù)adjust0和adjust1用于調(diào)整數(shù)據(jù),與本題求解無關(guān))。請返回一個(gè)bool值代表它們是否相交。

思路

兩個(gè)有環(huán)鏈表如果相交,只存在圖示三種情況.
所以首先我們都要找到兩個(gè)鏈表的入環(huán)節(jié)點(diǎn)entry1和entry2.如果entry1==entry2,則屬于情況(1)或者(2),直接返回true即可.
否則從entry1或者entry2開始遍歷,繞環(huán)一圈,如果中途發(fā)現(xiàn)有等于另一個(gè)entry的點(diǎn),則說明屬于(3). 否則就是不相交的兩個(gè)有環(huán)鏈表.

有環(huán)鏈表相交的三種情況

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class ChkIntersection {
    public boolean chkInter(ListNode head1, ListNode head2, int adjust0, int adjust1) {
        ListNode entry1=findCycleEntry(head1);
        ListNode entry2=findCycleEntry(head2);
        if(entry1==entry2){
          return true;
        }
        else{
            ListNode backup=entry1;
            do{
                entry1=entry1.next;
            }while(entry1!=entry2&&entry1!=backup);
            return !(entry1==backup);
        }
    }
  
    
    //找到入環(huán)節(jié)點(diǎn)
    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;
    }    
}