Linked List Cycle
2024-10-29 15:33:43
Given a linked list, determine if it has a cycle in it.
/**
* 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)
return false;
ListNode* fast = head->next;
ListNode* slow = head;
while(fast) {
if(fast == slow)
return true;
if(fast->next&&fast->next->next){//短路的技巧
fast = fast->next->next;
slow = slow->next;
}
else
return false;
}
return false;
}
};
设置两个指针,一个快指针,一个慢指针。快指针每次走两步,慢指针每次走一步,如果相遇就是有环。
19行先判断快指针能不能走1步,如果能在判断2步之后是不是链表末尾,如果不是末尾就可以向下走。
==============================我是分割线=============================================
《编程之美》上看到一道题目,判断两个两个链表(无环)是否相交,可以转化为这题的解法,把第二个链表头接到另一个的末尾,在检测是否有环,有环就是相交。
两一种解法更简单,比较倒数第二节链表是否相等。越来愈感受到算法的美妙了.QAQ
最新文章
- js-DOM-页面元素的兼容性、常用事件、节点
- MapReduce多线程下的错误
- 计算2的N次方
- MVC 将视图页table导出成excel
- AngularJs 入门系列-1 使用 AngularJs 搭建页面基本框架
- 一个IT人士的个人经历,给迷失方向的朋友
- 玩转ButterKnife注入框架
- UVA 10304 Optimal Binary Search Tree
- 前端开发必须说的那些事之——同源策略(same origin policy)
- Centos7安装和卸载Mongodb数据库
- 前端系列之JavaScript基础知识概述
- android官方技术文档翻译——aar 格式
- java--GUI(图形用户接口)
- early_suspend【转】
- UVa-1025城市里的间谍 A Spy in the Metro
- MySQL学习----索引的使用
- [转]mysql update case when和where之间的注意事项
- Vue.js学习笔记(一)
- use of _track and track_visibility
- plt-3D打印1