# Linked List Cycle II

## Question

* [Leetcode: Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/)
* [Lintcode: Linked List Cycle II](http://www.lintcode.com/en/problem/linked-list-cycle-ii/)

### Description

Given a linked list, return the node where the cycle begins.

If there is no cycle, return`null`.

### Example

Given`-21->10->4->5`, tail connects to node index 1，return`10`

### Challenge

Follow up:

Can you solve it without using extra space?

## 题解思路

可以先判断Linked List是否有Cycle，利用two pointers可以很快得到。接下来就要分析，快慢指针第一次相遇时，位置、步数和环的关系。

```
    a            b
A ------ B --------+
         |         |
       c |         |
         +-------- C



* A: 起始点
* B: Cycle Begins
* C: 1st 快慢指针相遇点


* A->B: a
* B->C: b
* C->B: c
* 环的长度 (b+c) 为 R
```

第一次相遇时，慢指针所走步数为

a + b

快指针走的步数为

a + b + nR

我们知道快指针是慢指针速度的2倍，因此

2(a + b) = a + b + nR

那么

a + b = nR

同时

b + c = R

所以

a = (n - 1)R + c;

也就是说，从A点和C点同时出发，以相同的速度前进，那么下一次相遇的位置将是B。

参考 LeetCode: <https://leetcode.com/articles/linked-list-cycle/>

## 源代码

Easier to understand:

```java
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
         if (head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while (slow != null && fast != null) {
            slow = slow.next;
            if (fast.next == null) return null;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        slow = head;
        if (fast != null) {
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
        return null;
    }
}
```

Preferred Implementation:

```java
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    private ListNode answer = null;
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {

            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                break;
            }
        }
        if (fast == slow) {
            slow = head;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
        return null;
    }
}
```

Harder to understand with pointer corner cases

```java
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next==null) {
            return null;
        }

        ListNode fast, slow;
        fast = head.next;
        slow = head;
        while (fast != slow) {
            if(fast==null || fast.next==null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
        } 

        while (head != slow.next) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/linked_list/linked_list_cycle_ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.