首页 > 代码库 > 142. Linked List Cycle II

142. Linked List Cycle II

题目:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

 

Hide Tags
 Linked List Two Pointers
 

链接: http://leetcode.com/problems/linked-list-cycle-ii/

6/11/2017

注意

第11,12行没有放在第7行是为了排除第一次最开始slow, fast都在head的情况,但是也不应该在第7行判断是否2者当时是head,有可能环的起点就是head

 1 public class Solution {
 2     public ListNode detectCycle(ListNode head) {
 3         if (head == null) {
 4             return head;
 5         }
 6         ListNode slow = head, fast = head;
 7         while (fast != null && fast.next != null) {
 8             slow = slow.next;
 9             fast = fast.next;
10             fast = fast.next;
11             if (slow == fast) {
12                 break;
13             }
14         }
15         if (fast == null || fast.next == null) {
16             return null;
17         }
18         fast = head;
19         while (fast != slow) {
20             fast = fast.next;
21             slow = slow.next;
22         }
23         return fast;
24     }
25 }

这道题应该是记下来的,但是分析不会

更多讨论

https://discuss.leetcode.com/category/150/linked-list-cycle-ii

142. Linked List Cycle II