程序员必看 c++笔试题汇总(1)(11)
45. 如何判断一个单链表是有环的?(注意不能用标志位，最多只能用两个额外指针) struct node { char val; node* next;} bool check(const node* head) {} //return false ： 无环
45. 如何判断一个单链表是有环的?(注意不能用标志位，最多只能用两个额外指针)
struct node { char val; node* next;}
bool check(const node* head) {} //return false ： 无环;true： 有环
一种O(n)的办法就是(搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然)：
- bool check(const node* head)
- {
- if(head==NULL) return false;
- node *low=head, *fast=head->next;
- while(fast!=NULL && fast->next!=NULL)
- {
- low=low->next;
- fast=fast->next->next;
- if(low==fast) return true;
- }
- return false;
- }
本篇文章只是笔者个人对程序员c++笔试题的一些个人总结，如果大家对以上内容有不同见解，也欢迎留言告之。
- 上一篇：C++的明天是否会依旧辉煌？
- 下一篇：深入剖析C/C++程序员应聘常见面试题
精彩图集
精彩文章