题解 | #链表中环的入口结点#

链表中环的入口结点

https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //1.设置一个快2步一个慢指针1步;
        ListNode fast = pHead;
        ListNode slow = pHead;
        ListNode ans= pHead;//开始时不出发,前两个相遇再出发
        int out=0;
        //2.在第一次相遇的时候,此时从head处新出发一个指针
        //这里有个bug,如果fast为null,那么fast.next是有问题的,会报错,需要注意
        while(fast.next!=null&&out!=1)
        {
            fast=fast.next.next;
            if(fast==null)
            break;
            System.out.println(fast==null);
            slow=slow.next;         
            if(slow==fast && fast!=null)
            {
                while(ans!=slow)
                {
                    slow=slow.next;
                    ans=ans.next;
                }
                out=1;
            }
        }

        //若没有环则返回空
        if(out==0)
        {
            return ans=null;
        }
        //3.两个慢指针相遇的时刻,就是入口    
        return ans;  
    }
}

全部评论

相关推荐

杨柳哥:这不是普通人,那这个钱的是天才
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务