面试题23：链表中环的入口节点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

知识点

链表

Qiang的思路

对于这个问题，我最先想到的是判断每一个节点的内存地址，如果有两个节点的内存地址相同，那么该节点肯定是环的入口节点，如果找不到这样的节点，那么一定没有环。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        ids=[]
        while pHead!=None:
            if id(pHead) in ids:
                return pHead
            ids.append(id(pHead))
            pHead=pHead.next
        return None

两个节点的内存地址相等就是两个节点相等。

Book中的思路

书中的做法一共分了三步：

• 判断是不是有环
• 得到环的大小
• 寻找环的入口

在第一步中，通过设置两个指针，一个每次走一步，一个每次走两步，这样如果有环的话，走的快的指针就能追上走的慢的指针，如果没有环的话走得快的指针就会遇到空节点。

第二步是紧接着第一步进行的，在两个指针相遇之后，我们就能够知道当前节点在环中，所以从当前节点开始遍历，必然会回到该节点，那么这个长度就是环的大小。

第三步同样需要设置两个指针，一个在前一个在后，在前的距离在后的距离恰恰是环的长度，这样同时开始遍历，当两个指针相遇时的节点就是环的入口节点。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        p1=pHead
        p2=pHead
        flag=False
        while p2!=None and p2.next!=None:
            p2=p2.next.next
            if p1==p2:
                flag=True
                break
            p1=p1.next
        if flag==False:
            return None
        count=1
        p1=p1.next
        while p1!=p2:
            p1=p1.next
            count+=1
        p1=pHead
        p2=pHead
        for i in range(count):
            p2=p2.next
        while True:
            if p1==p2:
                return p1
            p1=p1.next
            p2=p2.next

这个代码我调了一下午（心累），最后发现问题在于判断是否有环的循环已进入两个指针是相等的，所以不能之间判断两个指针是否相等，因为此刻他们一定相等，所以我将快指针的更新放在了循环的开始，这样便可以避免这一个问题了。

作者的这种做法时间复杂度要低于我的做法，因为我的需要对每个节点与其之前的节点进行比较是否相等，这就是O(n^2)的时间复杂度，但是作者通过三次遍历，每次都是线性的，所以总体的复杂度要低，可能系数高一些。从理解上来说可能我的更简单一些吧。

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。