题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
说明：本题目包含复杂数据结构ListNode，点此查看相关信息

  1. # -*- coding:utf-8 -*-
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  6. class Solution:
  7.     def EntryNodeOfLoop(self, pHead):
  8.         # write code here
  9.         if not pHead or not pHead.next:
  10.             return None
  11.         p_slow = pHead
  12.         p_fast = pHead
  13.         while p_slow and p_fast.next:
  14.             p_slow = p_slow.next
  15.             p_fast = p_fast.next.next
  16.             if p_slow == p_fast:
  17.                 break
  18.         p1 = pHead
  19.         p2 = p_slow
  20.         while p1!=p2:
  21.             p1 = p1.next
  22.             p2 = p2.next
  23.         return p1