请教一个题目:有环单链表相交判断练习题
题目地址:http://www.nowcoder.com/questionTerminal/af0b526dc7df4d9f8727433e6a48c338
题目:
如何判断两个有环单链表是否相交?相交的话返回第一个相交的节点,不想交的话返回空。如果两个链表长度分别为N和M,请做到时间复杂度O(N+M),额外空间复杂度O(1)。
给定两个链表的头结点head1和head2(注意,另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。
我的解答:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class ChkIntersection {
bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) {
ListNode *l1 = getFirstInCircleNode(head1);
ListNode *l2 = getFirstInCircleNode(head2);
if(l1==l2)return true;//入环节点相同,肯定是相交
else{//否则
ListNode *al1 = l1;
int flag = 0;
while(flag==0||al1!=l1){
flag = 1;
if(al1==l2)return true;//相交的另一种情形
al1=al1->next;
}
return false;//跳出循环后自动返回不相交
}
return false;
}
//下面这个函数是获取有环链表第一个入环节点,没有返回NULL
ListNode *getFirstInCircleNode(ListNode* head){
ListNode *f,*s;//分别是快指针和慢指针
f=s=head;
while(f!=NULL&&f!=s){
f=f->next;//快走一步
s=s->next;//慢走一步
if(f!=NULL){//快再走一步 f=f->next;
}//由于明确了是有环链表,故不判断else了,其实上面的if个人认为也不需要
}
f=head;
while(f!=s){
f=f->next;
s=s->next;
}
return f;
}
};
实在找不出哪里错了,但是提交总是返回错误,求大神指教! 错误提示: