链表19---循环链表，找到链表循环的起始位置

1、题目：

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?

2、解答： 先用两个指针，一个走一步，一个走两步，它们若相遇一定在链表的循环中，然后另外一个指针从头开始走，slow指针也一步一步的走，若它们相遇，便是起始位置

3、C++代码

class Solution { public: ListNode *detectCycle(ListNode *head) { if(head == NULL|| head->next == NULL) return NULL; ListNode *slow = head,*fast = head,*entry = head; while(fast->next && fast->next->next){ slow = slow->next; fast = fast->next->next; if(slow == fast){ while(slow != entry){ slow = slow->next; entry = entry->next; } return entry; } } return NULL; } };

python代码

class Solution(object): def detectCycle(self, head): """ :type head: ListNode :rtype: ListNode """ if head == None or head.next == None: return None slow,fast,entry = head,head,head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next if fast == slow: while entry != slow: entry = entry.next slow = slow.next return entry return None