解答
思路
这是【单链表中是否有环，写出代码】的扩展题，可以划分到面试中难度最大的那一档中
没有思路，只能静下心来
找环的入口点，就是找到入口点是链表的第几个结点，设这个结点q是第a个,
head到q的长度是a, 两个指针相遇时离入口点的距离为t, 链表长度为L，环的长度为r
如果相遇，设slow走了s步，则fast走了2s
可得 2s = s+ nr ( n >= 0)
=> s = nr => a + t = nr => a + t = (n-1)r + r
=> a + t = (n -1)r + L – a => a = (n-1)r + (L – a – t)
L – a – t 为相遇点到环入口点的距离
得到结论
设置两个指针，一个放在相遇点，一个放在链表头结点，当两者第一次相遇时，就得到环入口点P
实在不理解，可以只记住这个结论
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | Node findLoopNode(Node head){ //先找到相遇点，与例三一致 Node slow = head, fast = head; while ( fast && fast.next ) { slow = slow.next; fast = fast.next.next; if ( slow == fast ) break; } if (fast == null || fast.next == null); return null; //从相遇点开始到与头结点相遇 slow = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast;} |
不会，啊啊，我是废物
两个指针，快和慢
两个指针，一个块一个慢
两个指针，一个快一个慢。
两个指针，一个快一个慢，如果两个重叠就有环，否则没有
记录每一个next指针
记录每一个next指针 出现第二次的next指针则为入口 至于怎么记录 当然是使用hash 查找的时间复杂度为1 单链表遍历一遍就感觉出结果了