做书app下载网站有哪些/站长之家论坛

写在头部的后记：csdn的排版真是麻烦，本意是想完善一下这个博文，但不想现在偶尔会出现代码显示不全的现象，我又重新写了一个，若是影响阅读的话，大家可以去这个。

传送门：http://blog.csdn.net/w417950004/article/details/78229347

在C++下，创建单链表并输出单链表的值：

#include<iostream>
#include<stdlib.h>>
using namespace std;struct ListNode{int val;ListNode *next;};class Solution{public: bool hasCycle(ListNode *head){if(head==NULL||head->next==NULL){return false;}ListNode *slow,*fast;slow=head;fast=head;
//          ListNode *slow=head;
//          ListNode *fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow)return true;cout<<"标记2！";}cout<<"标记1！";return false;}
};
//构造链表是正确的
void build_list(ListNode *p){int vals;cout << "Input numbers!" << endl;while((cin>>vals)){
//        temp->val=vals;ListNode *t;t=(ListNode*)malloc(sizeof(ListNode));t->val=vals;p->next=t;p=p->next;}}int main()
{Solution sot;bool result;ListNode *p,*head;p=head;build_list(p);//输出cout<<"result is :"<<endl;for(p=head->next;p!=NULL;p=p->next){cout<<p->val<<"  ";}cout<<endl<<endl;result=true;result=sot.hasCycle(head->next);if(result)                //if result is true,there habe cycle,else notcout<<"There have cycle!"<<endl;elsecout<<"There no cycle!"<<endl;return 0;
}

原本是Leetcode上的一个题目，在不借用额外空间下求单链表是否有循环。但是创建了单链表之后，不知道如何才能将单链表的弄成循环的，所以就仅仅是输出啦。

注意：这种方法的主要思想是定义两个指针fast和slow，slow每次走一步而fast一次走两步，最终如果没环的话，

链表遍历一遍就结束了；若是有环的话，快的链表肯定会与慢的链表重合的。

之前一直有个思维误区，在有环的情况下fast一次跳两步会不会正好把slow跳过去呢？

后来发现是我多虑了，因为是每次一人走一步的，除了在起点fast在环内是一直在slow后面的，而fast最接近slow的时候是离slow只有一步(就是fast->next是slow)或者是两步的。而fast离slow最近的时候两步之内肯定能追上slow。有兴趣的同学可以想一想就算是fast每次走三步，也是完全可以和slow碰面的。只不过要加一条判断语句。

slow=slow->next;
if(fast==slow)return true;
fast=fast->next->next;

至于原因嘛，~ _ ~ 你肯定能想到的。