剑指Offer：链表中环的入口点（Python）

雨点打透心脏的1/2处 2023-07-17 09:48 14阅读 0赞

## 题目 ##

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

## 思路 ##

把链表中节点值放到dict数组中，并记录出现的次数，如果出现次数超过一次，则为环的入口节点。

## 解答 ##

**方法一**

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    class Solution:
        def EntryNodeOfLoop(self, pHead):
            if pHead is None:
                return None
            num, dict, flag = [], {}, True
            tempans = 0
            while pHead and flag == True:
                num.append(pHead.val)
                numset = set(num)
                for c in numset:
                    dict[c] = 0
                for c in num:
                    dict[c] += 1
                for c in num:
                    if dict[c] > 1:
                        flag = False
                        tempans = c
                pHead = pHead.next
            while pHead:
                if pHead.val == tempans:
                    return pHead
                pHead = pHead.next
            return None

## 思路 ##

快慢指针

**方法二**

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    class Solution:
        def EntryNodeOfLoop(self, pHead):
            if pHead == None:
                return None
            p = pHead
            q = pHead
            while p and p.next:
                p = p.next.next
                q = q.next
                if p == q:
                    break
            if p == None or p.next == None:
                return None
            p = pHead
            while p != q:
                p = p.next
                q = q.next
            return p