剑指offer-链表中环的入口结点-链表-python ***
2024-09-21 00:44:19
题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
思路
第一步,用两个快慢指针找环中相汇点。分别用slow
, fast
指向链表头部,slow
每次走一步,fast
每次走二步,直到fast == slow
找到在环中的相汇点。
第二步,找环的入口。当fast == slow
时,假设slow
走过x个节点,则fast
走过2x个节点。设环中有n个节点,因为fast
比slow
多走一圈(n个节点),所以有等式2x = n + x
,可以推出n = x
,即slow
实际上走了一个环的步数。这时,我们让fast
重新指向链表头部pHead
,slow
的位置不变,然后slow
和fast
一起向前每次走一步,直到fast == slow
,此时两个指针相遇的节点就是环的入口。
# -*- 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 is None:
return None
if pHead.next is None:
return None
p = pHead
q = pHead.next
while p!=q:
if q.next is not None and q.next.next is not None:
p = p.next
q = q.next.next
else:
break
if p ==q:
r = pHead
p = p.next
while r != p:
r = r.next
p = p.next
return r
else:
return None
最新文章
- 前端之css
- 【转】【RDS教程】专业DBA速成 - CPU优化篇
- soap request by afnetworking2.X/3.X
- SQLServer性能调优3之索引(Index)的维护
- 运用Mono.Ceci类库修改.NET程序集 走上破解软件的道路
- 将helps.php或者functions.php直接进行了加载
- 20150626_Andriod_02_ListView2_列表与详细信息
- vi编辑器基本用法介绍
- Asp与Asp.Net的区别
- Python使用ctypes访问C代码
- WPF中ContextMenu通过CommandParameter传参
- Java对象中的finalize()方法使用说明
- HeapAlloc,GlobalAlloc,LocalAlloc,VirtualAlloc,malloc,new的异同
- [Alibaba-ARouter] 简单好用的Android页面路由框架
- Linux下配置yum源为阿里云或网易的详解
- OnCheckedChangeListener和setChecked之间冲突问题解决
- Python中re(正则表达式)模块学习
- 在VMware中使用Nat方式设置静态IP, 宿主机可以 ssh
- C#编程(四十五)----------格式字符串
- vue elementui switch开关控件的使用