23-链表中环的入口节点

题目：如果一个链表中包含环，如何找出环的入口节点。

# 找出环状链表的分支结点
def has_cir(head):
    if not head:
        return False
    p = head
    q = head
    while p:
        p=p.next
        if p:
            p=p.next
        else:
            return False
        q = q.next
        if p==q:
            return True

# 找出环内结点个数
def node_count_cir(head):
    cnt = 1
    if has_cir(head):
        p,q = head,head.next.next
        while True:
            if p == q:
                break
            p=p.next
            q=q.next.next

        p2=p.next
        while p2!=p:
            p2=p2.next
            cnt+=1
        return cnt

    return 0

# 找出环内第一个结点
def node_first_cir(head):
    node_cnt_cir = node_count_cir(head)
    p,q=head,head
    for i in range(node_cnt_cir):
        p=p.next
    while p!=q:
        p=p.next
        q=q.next
    return p.data

注：

本题要找出环的入口节点，主要分三步：

1、判断该链表是否有环（使用快慢指针，如果相遇则证明有环）

2、如果有环，则快慢指针的相遇点必在换内，这一步判断换内节点总数（从该节点遍历，直到回到该节点的长度）

3、使用两个指针，第一个指针先走环内节点数量的步数，然后两个指针同时往后遍历，当两个指针指到同一个节点时，即为环的入口点