题解 | #链表中环的入口结点#
链表中环的入口结点
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) { ListNode dummy = new ListNode(-1), slow = dummy, fast = dummy, p = dummy, q = null; boolean f = false; dummy.next = pHead; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if(slow == fast) { f = true; q = slow; } if(f) { p = p.next; q = q.next; if(p == q) return p; } } return null; } }
判断链表有无环的升级版。当快慢指针相遇时,设置两个指针p,q;p从头出发,q从slow出发,两指针相遇就是环的入口