方法一:
使用哈希Set存储访问过的结点,第一个在Set中重复出现的结点就是入口结点
public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode pnt = pHead; Set<ListNode> set = new HashSet<>(); while(pnt != null){ if(set.contains(pnt)) return pnt; set.add(pnt); pnt = pnt.next; } return null; }
方法二:双指针法:
建立两个快慢指针,首先使用快慢指针找到交点;
然后让slow回到原点,两个指针以相同速度向前运行,当两个结点再次相遇的时候,就是链表的入口结点。
public static class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if (pHead == null || pHead.next == null) return null; ListNode fast = isLoop(pHead); // find the point we meet if(fast ==null) return null; System.out.println(fast.val); ListNode slow = pHead; while (slow != fast) { fast = fast.next; slow = slow.next; } return fast; } ListNode isLoop(ListNode pHead) { ListNode slow = pHead, fast = pHead; while (fast!=null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(slow == fast) break; } if(fast == null || fast.next == null) return null; return fast; } }