链表中环的入口结点

链表中环的入口结点

http://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4

思路:
这里可以自己画图列一下方程。
快慢指针法,快指针一次走两步,慢指针一次走一步,当快慢指针第一次相遇时图片说明
2(x+y)=n圈周长+x+y,
这里x+y是慢指针走的长度,n圈周长+x+y是快指针走的长度
x = n
圈周长-y;
即当快指针回到head和慢指针以同样速度每次走一步,最终会在链表中环的入口结点处相遇。

 public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead==null||pHead.next==null||pHead.next.next==null) return null;
        ListNode slow = pHead.next;
        ListNode fast = pHead.next.next;
        while(slow!=fast){
            if(slow==null||fast.next==null) return null;
            slow = slow.next;
            fast = fast.next.next;

        }
        fast=pHead;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
全部评论
不知道为啥,slow初值设为pHead、fast初值设为pHead.next会超时
点赞 回复 分享
发布于 2020-03-30 17:13
画完示意图,列完方程才明白,感谢!
点赞 回复 分享
发布于 2020-03-14 21:09

相关推荐

Java面试先知:我也是和你一样的情况,hr 说等开奖就行了
点赞 评论 收藏
分享
代码飞升_不回私信人...:别这样贬低自己,降低预期,放平心态,跟昨天的自己比。做好自己,反而会效率更高心态更好,加油兄弟
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

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