leetcode 141 142. Linked List Cycle
2024-08-27 13:00:48
题目描述:
不用辅助空间判断,链表中是否有环
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/*一个指针走的快 一个指针走得慢*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL)
return false;
ListNode *first = head;
ListNode *Second = head;
while(Second->next != NULL){ first = first->next;
Second = Second->next->next;
if(Second == NULL)
return false;
if(Second == first)
return true;
}
return false;
}
};
142 找到环开始的结点
第一次相遇时slow走过的距离:a+b,fast走过的距离:a+b+c+b。
因为fast的速度是slow的两倍,所以fast走的距离是slow的两倍,有 2(a+b) = a+b+c+b,可以得到a=c(这个结论很重要!)。
/**
* 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) {
if(head == NULL)
return NULL;
ListNode *first = head;
ListNode *second = head;
bool flag = true;
while(second->next != NULL){
first = first->next;
second = second->next->next;
if(second == NULL)
return NULL;
if(first == second){
flag = false;
break;
}
}
if(flag == true)
return NULL;
first = head;
while(first != second){
first = first->next;
second = second->next;
}
return first; }
};
最新文章
- tp框架实现ajax
- 苹果手机微信上form表单提交的问题
- Html/Css(新手入门第三篇)
- 多个div居中显示
- sql server 2008数据复制
- POJ 2409 Let it Bead(Polya定理)
- c/s架构
- git 与 github基本使用
- 单行json_ajax
- Java基本数据类型的长度范围
- 第三篇:爬虫框架 - Scrapy
- JVM堆内存监测的一种方式,性能调优依旧任重道远
- 【javascript】数据类型中的一些小知识点
- JAVA REENTRANTLOCK、SEMAPHORE 的实现与 AQS 框架
- JQuery Plugin 开发
- Advanced Wlan Attacks (RADIUS)
- ionic cordova 安装指定版本
- 在windows端使用jupyter notebook,服务器充当后台计算云端 简化描述
- BeautifulSoup爬虫基础知识
- ASP.NET绑定CHECKBOXLIST--------JQUERY绑定CLICK事件,获取CHECKBOX的VALUE和显示值
热门文章
- [洛谷P5169]xtq的异或和
- P2672 推销员 优先队列 + 贪心
- BZOJ3631:[JLOI2014]松鼠的新家——题解
- ZOJ2314:Reactor Cooling——题解
- Rabbitmq----基础使用
- [异常处理]class kafka.common.UnknownTopicOrPartitionException (kafka.server.ReplicaFetcherThread)
- c# 合并两个有序数组
- 任务调度 Quartz 学习(一) SimpleTrigger
- opencv在property panel中新建一行
- 省队集训Day1 总统选举