剑指offer刷题笔记55（python）

题目描述

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

思路

设置一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步。如果存在环的话，快慢指针除了头节点之外，一定会在碰上。 假设，入口节点和头结点之间的距离为a（绿线），第一次相遇节点和入口节点之间的距离为b（蓝线），链表剩下的长度为c（红线），那么第一次相遇的时候，慢指针走的长度是a + b，快指针走的长度是a + b + c + b，因为快指针每次走两步，因此2（a + b）=（a + b + c + b），可以推出a = c。因此在快慢指针相遇的时候，令快指针再从头开始一步一步的走，这是两个指针再次相遇的节点就是入口节点。

代码

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def EntryNodeOfLoop(self, pHead): # write code here if pHead == None : return None if pHead.next == None: return None fast = pHead.next.next slow = pHead.next # 要注意原链表可能没有环先判断，即如果快指针到链表尾部都没有slow == fast， # 则说明没有环。返回None while fast != slow: if fast.next != None and fast.next.next != None: fast = fast.next.next slow = slow.next else: return None # 如果有环，fast = PHead fast = pHead while fast != slow: fast = fast.next slow = slow.next return slow