leetcode 【 Linked List Cycle II 】 python 实现
2024-09-28 03:51:08
公司和学校事情比较多,隔了好几天没刷题,今天继续刷起来。
题目:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
Follow up:
Can you solve it without using extra space?
代码:oj 测试通过 Runtime: 596 ms
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None class Solution:
# @param head, a ListNode
# @return a list node
def detectCycle(self, head):
if head is None or head.next is None:
return None dummyhead = ListNode(0)
dummyhead.next = head p1 = ListNode(0)
p1.next = head
p2 = ListNode(0)
p2.next = head first_meet = None
while p1 is not None and p2 is not None:
if p1 == p2:
first_meet = p1
break
else:
p1 = p1.next
p2 = p2.next
if p2 is not None:
p2 = p2.next result = None
if first_meet is None:
return None
else:
p2 = dummyhead
while p1 is not None and p2 is not None:
if p1.next == p2.next:
result = p1.next
break
else:
p1 = p1.next
p2 = p2.next
return result
思路:
主要利用快慢指针的思想。
自己没太多思路,直接参考下面几篇靠谱的日志:
http://www.cnblogs.com/hiddenfox/p/3408931.html
http://blog.csdn.net/cs_guoxiaozhu/article/details/14209743
如果链表中没有循环自不必说;
如果有循环:
快慢指针第一次相遇之后,把一个指针重新指向head,然后两个指针相同速度往前走;
两个指针第二次相遇的位置就是循环开始的位置
Tips:
自己在实现的时候犯了一个错误,迭代p1 p2 找到二次相遇的位置 直接返回p1,这里迷糊了:应该迭代p1 p2判断p1.next与p2.next相等,再返回p1.next;这样返回的点才是原来链表中的,而不是构造出来的p1。
最新文章
- Android中点击隐藏软键盘最佳方法——Android开发之路4
- javascript-装饰者模式
- ShellExecute —— 运行一个外部程序
- <;转>;boost 1.53 and STLPort build binary for windows
- 基于SpringMVC的增删改查
- openwrt-智能路由器hack技术(2)---";网路信息监控和窃取";
- nutz的json视图
- SQL Server排序规则
- ExtJs中实现tree节点,全部是单击展开和收缩效果,和收藏夹点击功能一样
- Delphi RichEdit操作
- Scope Chain(作用域链)
- WP8开发札记(二)让程序支持锁屏运行
- H5 Video + DOM
- postgresql 异步流复制hot standby搭建
- Javassist字节码增强示例
- Excel藏的很深(1)
- java数组的声明、创建和遍历
- Python3自定义http/https请求拦截mitmproxy脚本
- Linux网络编程:基于UDP的程序开发回顾篇
- webpack快速入门——集中拷贝静态资源
热门文章
- cms系统-帖子页面
- 让SAP云平台上的Web应用使用destination服务
- IDEA 编辑器如何将tabs 分行显示
- 【洛谷3527】[POI2011] MET-Meteors(树状数组+整体二分)
- python_35_进度条
- dojo/Deferred类和dojo/promise类的使用
- 在mac下使用python抓取数据
- 新装Ubuntu后的一些配置
- 【贪心 二分图 线段树】cf533A. Berland Miners
- 转:CentOS7 下 Redis4 安装与配置教程(Redis开机启动)