public class Solution {

    public ListNode detectCycle( ListNode head ) {

        if( head == null || head.next == null ){

            return null;

        }

        // 快指针fp和慢指针sp，

        ListNode fp = head, sp = head;

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

            sp = sp.next;

            fp = fp.next.next;

            //此处应该用fp == sp ，而不能用fp.equals(sp) 因为链表为1 2 的时候容易

            //抛出异常

            if( fp == sp ){  //说明有环

                break;

            }

        }

        //System.out.println( fp.val + "   "+ sp.val );

        if( fp == null || fp.next == null ){

            return null;

        }

        //说明有环，求环的起始节点

        sp = head;

        while( fp != sp ){

            sp = sp.next;

            fp = fp.next;

        }

        return sp;

    }

} 　　

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

    def __str__(self):

        if self:

            return "{}".format(self.val)

        else:

            return None

class Solution:

    # @param head, a ListNode

    # @return a list node

    def detectCycle(self, head):

        fast, slow = head, head

        while fast and fast.next:

            fast, slow = fast.next.next, slow.next

            if fast is slow:

                fast = head

                while fast is not slow:

                    fast, slow = fast.next, slow.next

                return fast

        return None　　

class Solution {

public:

    ListNode *detectCycle(ListNode *head) {

        ListNode *slow = head, *fast = head;

        while (fast && fast->next) {

            slow = slow->next;

            fast = fast->next->next;

            if (slow == fast) break;

        }

        if (!fast || !fast->next) return NULL;

        slow = head;

        while (slow != fast) {

            slow = slow->next;

            fast = fast->next;

        }

        return fast;

    }

};