请教一个题目:有环单链表相交判断练习题

题目地址:http://www.nowcoder.com/questionTerminal/af0b526dc7df4d9f8727433e6a48c338
题目:
如何判断两个有环单链表是否相交?相交的话返回第一个相交的节点,不想交的话返回空。如果两个链表长度分别为N和M,请做到时间复杂度O(N+M),额外空间复杂度O(1)。
给定两个链表的头结点head1head2(注意,另外两个参数adjust0adjust1用于调整数据,与本题求解无关)。请返回一个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;  
    }
};
实在找不出哪里错了,但是提交总是返回错误,求大神指教!
错误提示:

全部评论
求助
点赞 回复 分享
发布于 2016-03-05 00:27
自己发现问题了, 哎, getFirstInCircleNode 这个函数返回的总是头结点~,应该让s和f分别先走一两步再来循环比较的。
点赞 回复 分享
发布于 2016-03-05 09:36

相关推荐

评论
点赞
收藏
分享
牛客网
牛客企业服务