也是一道408真题,
【方法一】
之前的思路是
第一步:求两个链表的长度,并计算两个链表的长度之差step
第二步:长链表指针向前先走step步
第三步:锻炼表指针从头开始,长链表指针从step位置开始向前同步遍历,在交点处两个指针相等。
【方法二】
现在来整理第二个更加简单的思路
分别为链表A和链表B设置指针A和指针B,然后开始遍历链表,如果遍历完当前链表,则将指针指向另外一个链表的头部继续遍历,直至两个指针相遇。
最终两个指针分别走过的路径为:
指针A :a+c+b
指针B :b+c+a
明显 a+c+b = b+c+a,AB两个人走的路程一样,速度一样,一定会相遇
因而如果两个链表相交,则指针A和指针B必定在相交结点相遇。
需要注意的是如何判断没有交点的情况。
判断A!=null而不是A->next!=null
如果是 A=A->next!=NULL?A->next:headB; 那么AB指针永远都不会是null,导致while陷入死循环。
如果是 A=A!=NULL?A->next:headB;那么AB指针有机会是null,并且一旦是null一定是同时为null(因为走过的路程一样),此时A==B,跳出while循环!
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *A=headA,*B=headB;
while(A!=B){
A=A!=NULL?A->next:headB;
B=B!=NULL?B->next:headA;
}
return A;
}
下面这个是用flag来判断是否是第二次到达表尾,以确定是否没有交点 ,这样也是对的,但是代码就不优美了嘛~
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL||headB==NULL)return NULL;
ListNode *A=headA;
ListNode *B=headB;
int flagA=0,flagB=0;
while(A!=B){
if(A->next!=NULL){
A=A->next;
}
else{
flagA++;//记录到达链表尾部的次数,如果两次到达链表尾部说明没有交点
if(flagB==2)return NULL;
A=headB;
}
if(B->next!=NULL){
B=B->next;
}
else {
flagB++;
if(flagB==2)return NULL;
B=headA;
}
}
return A;
}
};