题解 | #链表中环的入口结点#
链表中环的入口结点
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; } }