求两个链表是否有交点和交点位置。
先判断是否有环。如果两者一个有一个没有,一定没有交点。
两者无环
思路很简单:先求两者长度,然后较大者先从头指针出走m步,m是两者长度差值。然后两指针同时开始走,如果两者有交,则两指针一定会在某一点相遇。如果不是,则两指针在都为空之前均不相等。
CODE
bool chkIntersect(ListNode* headA, ListNode* headB) {
if(!headA || !headB)
return false;
int len1=ListLen(headA);
int len2=ListLen(headB);
if(len1>len2){
for(int i=0;i<len1-len2;i++){
headA=headA->next;
}
}else{
for(int i=0;i<len2-len1;i++){
headB=headB->next;
}
}
while(headA){
if(headA==headB)
return true;
headA=headA->next;
headB=headB->next;
}
return false;
}
两者有环
如果两者有环,那么交点可能在入环前,或入环后。
-
找到两者入环结点,如果相等,则交点在入环前。使用“两者无环”情况的思路,以入环结点为尾结点,求出两链表长度,然后错位遍历。
-
如果两入环结点不相等:
这种情况下,可能是无交,或者交点在环内。方法是其中一个入环结点(比如node2)沿着所在环遍历一遍回到原来位置,如果node1也在环内,两者就会相遇。反之,两者就是无交。
CODE
函数1:判断是否有环,返回入环结点
ListNode* chkLoop(ListNode* head) {
if(!head || !head->next)
return nullptr;
ListNode* H=new ListNode(0);
H->next=head;
ListNode *fast=H,*slow=H;
while(fast->next && fast->next->next){
fast=fast->next->next;
slow=slow->next;
if(fast==slow){
break;
}
}
if(fast!=slow)
return nullptr;
slow=H;
while(fast!=slow){
fast=fast->next;
slow=slow->next;
}
delete H;
return fast;
}
函数2:求链表的长度,截止于参数2之前的位置
int ListLen(ListNode* h,ListNode* tnext){
int len=0;
while(h!=tnext){
len++;
h=h->next;
}
return len;
}
这样的话,当tnext==NULL时就是求整个链表的长度。
函数3:已知两个链表均以tnext做尾后,求是否相交
ListNode* rLinkJoint(ListNode* headA, ListNode* headB,ListNode* tnext) {
if(!headA || !headB)
return nullptr;
int len1=ListLen(headA,tnext);
int len2=ListLen(headB,tnext);
if(len1>len2){
for(int i=0;i<len1-len2;i++){
headA=headA->next;
}
}else{
for(int i=0;i<len2-len1;i++){
headB=headB->next;
}
}
while(headA!=tnext){
if(headA==headB)
return headA;
headA=headA->next;
headB=headB->next;
}
return nullptr;
}
这样的话,当tnext==NULL时就是正常无环链表的情况。
函数4:判断情况以及交点在入环部分的代码
bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) {
ListNode *join1=chkLoop(head1),*join2=chkLoop(head2);
if(!join1 && !join2){
return rLinkJoint(head1, head2,nullptr);
}else if(join1 && join2){
if(join1==join2){
return rLinkJoint(head1, head2,join1->next);
}else{
ListNode *p=join1;
do{
if(p==join2)
return true;
p=p->next;
}while(p!=join1);
return false;
}
}else
return false;
}
思考
链表以NULL做尾后,我们也可以自己知道尾后参数,来增加函数的
网友评论