【Leetcode】Linked List Cycle II
2024-08-31 22:52:56
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?
思路:由【Leetcode】Linked
List Cycle可知。利用一快一慢两个指针可以推断出链表是否存在环路。
如果两个指针相遇之前slow走了s步,则fast走了2s步。而且fast已经在长度为r的环路中走了n圈,则可知:s = n * r。假定链表长为l。从链表头到环入口点距离为x。从环入口点到相遇点距离为a,则:x + a = s = n * r = (n - 1) * r + r = (n
- 1) * r + l - x。因此x = (n - 1) * r + (l - x - a)。(l - x - a)为从相遇点到环入口的距离,这意味着当一个指针从链表头出发时,还有一个指针从相遇点開始出发,两者一定会在环入口处相遇。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode * slow = head;
ListNode * fast = head; while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next; if(slow == fast)
{
ListNode *slow2 = head;
while (slow2 != slow)
{
slow2 = slow2->next;
slow = slow->next;
}
return slow2;
}
} return NULL; }
};
版权声明:本文博主原创文章,博客,未经同意不得转载。
最新文章
- 背水一战 Windows 10 (14) - 动画: 线性动画, 关键帧动画
- nginx.conf详解
- iOS开发小技巧--获取自定义的BarButtonItem中的自定义View的方法(customView)
- iOS 中关于ViewController总结
- Bootstrap之Carousel问题
- placeholder 兼容IE9以下版本 包含pasword
- Linux误删C基本运行库libc.so.6急救方法
- [置顶] Asp.Net---css样式的使用方式
- java 文件操作 写入和读取(小结一)
- 菜鸟玩云计算之十二:KVM虚拟机更改大小
- android binder理解
- HashMap源码调试——认识";put";操作
- 关于thinkphp5URL重写
- 通过Eureka自带REST API强行剔除失效服务
- Linux下创建C函数库
- day5模块学习--re正则模块
- vector erase的错误用法
- 【BZOJ4554】【TJOI2016】【HEOI2016】游戏
- VC中编译报错:error C2011: 'fd_set' : 'struct' type redefinition
- JavaScript快速入门-ECMAScript对象介绍