Leetcode 141. Linked List Cycle

2019-11-11 06:33:13

字体：大中小

来源：转载

供稿：网友

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

s思路： 1. 经典的题目！在这里突然想总结一下链表的操作：链表元素插入和删除；链表的单向移动。为实现链表元素插入和删除，可能的方法包括dummy node和pointer-to-pointer；为实现链表的单向移动，就不得不提快慢指针的移动方法了，不但可以检测是否有cycle，还可以找链表的中点。总之，快慢指针移动大法，都说好！我只好奇，第一个发明这个方法的人，是怎么想到这个方法的，又是来解决什么问题的？ 2. 这里简单介绍一下快慢指针法：如下图：

-快指针移动步数：a+b+(b+c)*n （在cyle里面移动n圈，n>=1）-慢指针移动步数：a+b-快指针移动速度是慢的2倍，所以：2a+2b=a+(n+1)b+nc-所以：a=(n-1)(b+c)+c;因此，相遇后，把快指针放到head,慢指针放在相遇的地方，相同的速度移动，则：快慢相遇的再次相遇的地方一定是cycle开始的地方，即：可以检查到cycle，以及break the cycle!

这里写图片描述

class Solution {public: bool hasCycle(ListNode *head) { // if(!head) return false; ListNode* fast=head->next,*slow=head;//bug:fast开始就要比slow快一个位置 while(fast&&fast!=slow){ fast=fast->next?fast->next->next:NULL; slow=slow->next; } return fast==slow; //return fast!=NULL;//两个条件都可以 }};

上一篇：一种正确调用自定义控件的方法

下一篇：Qt将图片保存为XML文件或者变为QSting