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

链表中环的入口结点

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

这里怎么说呢?其实就是涉及到一个推导公式,具体推导的过程就不写了,直接给出结论:快慢指针相遇的节点距离环的入口,等于头结点与环的距离。
所以第一步找快慢指针相遇的节点就好,直接拿我们前面求是否是一个环的题目代码来用
//寻找相遇的节点
    public ListNode same(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) return slow;
        }
        return null;
    }

然后直接求入口就行
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //快慢指针相遇节点的距离到环的距离和头结点到环的距离相等
        //首先找到相遇节点
        ListNode meetNode = same(pHead);
        if(meetNode == null) return null;
        while(pHead != meetNode){
            pHead = pHead.next;
            meetNode = meetNode.next;
        }
        return pHead;
    }
    
    //寻找相遇的节点
    public ListNode same(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) return slow;
        }
        return null;
    }
}


全部评论

相关推荐

点赞 评论 收藏
分享
只写bug的程序媛:才15,我招行20多万,建设银行50多万,说放弃就放弃
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务