无环单链表判相交练习题

现在有两个无环单链表，若两个链表的长度分别为m和n，请设计一个时间复杂度为O(n + m)，额外空间复杂度为O(1)的算法，判断这两个链表是否相交。
给定两个链表的头结点headA和headB，请返回一个bool值，代表这两个链表是否相交。保证两个链表长度小于等于500。

思路:

先得出两个链表的长度m和n, 比较m和n的大小,将长度较大的链表的头结点向前移动|m-n|个位置,然后将headA和headB一起移动.
为什么要移动|m-n|个位置? 是因为如果两链表相交,意味着他们从某一点之后就重合了,那么非重合部分的长度的差就是|m-n|,让稍长的链表先移动|m-n|步,他们就可以在重合的入口处相遇.

图片来自牛客网

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class CheckIntersect {
    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;
    }
}