【链表】NC3:链表中环的入口节点
发布于 2021-04-04 04:19
题目描述
对于一个给定的链表，返回环的入口节点，如果没有环，返回null
拓展：
你能给出不利用额外空间的解法么？
先判断链表是否有环，有环之后，再计算一下
借用一张图，可以简单画一画关系，得到a=c
因此fast=head先，fast从X到Y，slow从Z到Y，这样两者同速度走到Y正好是环的入口节点
public class Solution {public ListNode detectCycle(ListNode head) {if (head == null || head.next == null) {return null;}ListNode fast = head;ListNode slow = head;while (fast != null) {if (fast.next == null || fast.next.next == null) {return null;}fast = fast.next.next;slow = slow.next;if (fast == slow) {fast = head;while ( fast != slow) {fast = fast.next;slow = slow.next;}return fast;}}return null;}}
本文来自网络或网友投稿，如有侵犯您的权益，请发邮件至：aisoutu@outlook.com 我们将第一时间删除。
相关素材