1、Linked List Cycle II Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up: Can you solve it without using extra space? 判断一个链表有没有环常用快慢指针，之前有道题记录过，慢一步快两步，相遇就有环，遇到空指针就没有环，对于链表的环，一定是从尾节点连接到了前面某节点而成的。
寻找环开始的节点，简单推导一下～ 假设环开始节点距离头节点有x个节点距离，第一次相遇节点走过了环开始节点有y个节点距离，x，y均可为0； 当第一次相遇时： 慢指针一定走了x+y，则快指针就走了2(x+y)，快指针比慢指针多走了一圈，则环长一定是x+y；则慢指针再走x个节点就又回到了环开始的地方，也就是说，头节点和第一次相遇所在节点距离环开始节点相同。 第一次相遇后让头节点和慢指针一起走，相遇节点就是咯。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if(!head) return NULL; ListNode* slow=head; ListNode* fast=head; while(fast&&fast->next){ slow=slow->next; fast=fast->next->next; if(fast==slow){ while(slow!=head){ slow=slow->next; head=head->next; } return head; } } return NULL; } };