给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不想交的话返回false。
给定两个链表的头结点head1和head2(注意,另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个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;
}
}
网友评论