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

题目地址: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;  
    }
};
实在找不出哪里错了,但是提交总是返回错误,求大神指教!
错误提示:

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

相关推荐

10-29 16:42
门头沟学院 Java
1.今天什么国标的公司打电话约面试,还得准备ppt,好麻烦,网上查薪资一般,打算拒了,不面了2.字节又复活了,什么安全开发,也不知道怎么样,面一面试试吧,还是挺想去字节的,但好难,随缘吧所以今天没面试
嵌入式的小白:面试前可以好好准备下 1.看看你投递的岗位的岗位描述,分析下是哪个业务线,同使要罗列他们描述中提到的技术点 2.根据1中的两点准备 3.岗位描述中应该还有语言要求,这个刷刷八股,要是对自己语言能力很有把握,那就不用看这点了 4.找下你简历中项目部分,看有没有和岗位描述中技术点重合的,这种在面试提到项目时,是高概率问题 好好准备,祝你面试顺利
我的求职进度条
点赞 评论 收藏
分享
笑着秋招😊:我一直认为努力有回报是一件很幸福很幸福的事情,恭喜你
点赞 评论 收藏
分享
迷茫的大四🐶:都收获五个了,兄弟那还说啥,不用改了,去玩吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务