方法一:
使用哈希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; } }

京公网安备 11010502036488号