题目:
142. Linked List Cycle II(easy)
解题思路:
双指针典型例题。
首先利用快慢指针是否能够相遇,判断是否有环。
接着,在有环的基础上,假设起点到环起点长度为x
,环起点和相遇点的长度为y
,相遇点继续走到下次环起点的长度为z
。
已知:
slow走的路程:x+y
;fast走的路程:x+y+z+y
又因:
fast走过路程是slow路程的两倍:2*(x+y) = x+y+z+y
。得:x=z
所以,head到环起点距离 = 相遇点继续走到环起点得距离。

来自力扣的清晰解释
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| Java: public ListNode detectCycle(ListNode head) { ListNode fast = head,slow = head; while(true){ if(fast == null || fast.next == null) return null; fast = fast.next.next; slow = slow.next; if(slow == fast) break; } fast = head; while(fast != slow){ fast = fast.next; slow = slow.next; } return fast; }
|
v1.5.2