Leetcode-142Linked 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.

Note: Do not modify the linked list.

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

题解：

本题要求的是链表中存在的环的入口节点，如果不存在环，则返回NULL；
两种方法：
第一种方法很简单，使用集合set，每次在set中查找节点是否已存在，如果没有，将链表中节点存入set中，如果存在，则说明该位置为环的起始节点；
下面我们详细介绍下第二种方法，快慢指针；

image.png

如图：我们用fast表示快指针，每次移动两步；slow表示慢指针，每次移动一步；图中f1，s1分别对应着第一次移动是快慢指针移动后所指向的位置；可以看到，当快慢指针移动到第五步（f5，s5）时，他们相遇了；下面我们来分析下快慢指针相遇前经过的节点：
slow：节点1->2->3->4->5->6
fast：节点1->2->3->4->5->6->7->3->4->5->6
由于slow每次移动一步，fast每次移动两步，所以不难得出：
fast = 2*slow
所以得到：
(1->2->3->4->5->)6, 1->2->3(->4->5->6) =
(1->2->3->4->5->)6->7->3(->4->5->6)
删除带括号的重复部分，最终得到：
1->2->3 = 6->7->3
进行到这里，我们可以得出介样一个结论，辣就是从头结点（1）到环的起始节点（3）的距离等同于从快慢指针相遇的结点（6）到环的起始节点（3）的距离！！
最后给出快慢指针的C++实现以及set的Python实现：

My Solution1（C/C++完整实现）：

#include <cstdio>
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
};

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

int main() {
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    ListNode f(6);
    ListNode g(7);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    g.next = &c;
    Solution s;
    ListNode *result = s.detectCycle(&a);
    printf("%d\n", result->val);
    return 0;
}

结果：

3

Process returned 0 (0x0)   execution time : 0.023 s
Press any key to continue.

My Solution2（Python）：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        s = set('')
        while head:
            if head not in s:
                s.add(head)
            else:
                return head
            head = head.next
        return None