現(xiàn)在有兩個(gè)無(wú)環(huán)單鏈表眠副，若兩個(gè)鏈表的長(zhǎng)度分別為m和n腾啥，請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n + m)芋类，額外空間復(fù)雜度為O(1)的算法霜旧，判斷這兩個(gè)鏈表是否相交错忱。
給定兩個(gè)鏈表的頭結(jié)點(diǎn)headA和headB儡率，請(qǐng)返回一個(gè)bool值，代表這兩個(gè)鏈表是否相交以清。保證兩個(gè)鏈表長(zhǎng)度小于等于500儿普。
思路:
先得出兩個(gè)鏈表的長(zhǎng)度m和n, 比較m和n的大小,將長(zhǎng)度較大的鏈表的頭結(jié)點(diǎn)向前移動(dòng)|m-n|個(gè)位置,然后將headA和headB一起移動(dòng).
為什么要移動(dòng)|m-n|個(gè)位置? 是因?yàn)槿绻麅涉湵硐嘟?意味著他們從某一點(diǎn)之后就重合了,那么非重合部分的長(zhǎng)度的差就是|m-n|,讓稍長(zhǎng)的鏈表先移動(dòng)|m-n|步,他們就可以在重合的入口處相遇.
圖片來(lái)自牛客網(wǎng)
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;
}
}
