有关链表的LeetCode做题笔记合集，Python实现
链表定义
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
142. 环形链表 II Linked List Cycle II
第一种方法还是上面的用哈希表set来记录，占用空间
class Solution(object):
# 1.set记录
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
rec = []
curr = head
while curr:
if curr in rec:
return rec[rec.index(curr)]
rec.append(curr)
curr = curr.next
return None
第二种方法用快慢指针，先如上题一样检测是否有环，有的话设置一个新的检测节点从头(head)开始迭代，同时slow节点也继续迭代，直到二者相遇的点就是环的入口节点。
原理：
首先，头结点到入环结点的距离为a，入环结点到相遇结点的距离为b，相遇结点到入环结点的距离为c。然后，当f以s的两倍速度前进并和s相遇时，f走过的距离是s的两倍，即有等式：a+b+c+b = 2(a+b) ，可以得出 a = c ，所以说，让fast和slow分别从相遇结点和头结点同时同步长出发，他们的相遇结点就是入环结点。
当快、慢指针同时从入环点出发，那么一定会在入环点相遇。如果快、慢指针同时从入环点前一节点出发，那么快慢、指针则会在入环点的前一节点相遇，以此类推。
class Solution(object):
# 2.快慢指针
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow = fast = head
while slow and fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
detection = head
while slow != detection:
slow = slow.next
detection = detection.next
return detection
return None
