题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路一
迭代遍历链表，利用HashSet将每个结点添加到哈希表中，如果添加失败（重复遍历了这个结点即遇到环），输出该结点为环入口
实现
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ import java.util.HashSet; public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead == null) return pHead; HashSet hash = new HashSet(); while(pHead != null){ boolean chk = hash.add(pHead); if(chk == false) return pHead; pHead = pHead.next; } return null; } }
运行时间：17ms
占用内存：9608k
思路二
使用双指针，一个指针 fast 每次移动两个节点，一个指针 slow 每次移动一个节点。因为存在环，所以两个指针必定相遇在环中的某个节点上。假设相遇点在下图的 z1 位置，此时 fast 移动的节点数为 x+2y+z，slow 为 x+y，由于 fast 速度比 slow 快一倍，因此 x+2y+z=2(x+y)，得到 x=z。
在相遇点，slow 要到环的入口点还需要移动 z 个节点，如果让 fast 重新从头开始移动，并且速度变为每次移动一个节点，那么它到环入口点还需要移动 x 个节点。在上面已经推导出 x=z，因此 fast 和 slow 将在环入口点相遇。
实现
public ListNode EntryNodeOfLoop(ListNode pHead) { if (pHead == null || pHead.next == null) return null; ListNode slow = pHead, fast = pHead; do { fast = fast.next.next; slow = slow.next; } while (slow != fast); fast = pHead; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; }