问个今天的面试题：static成员函数在编译的时候和普通成员函数

2.如果没环的话最后结点p->next = NULL,否则p->next != NULL,让两个指针从头结点开始，以不同速度遍历，如果有环，两个指针会相等。 假如头结点为link * head. link * p,*q; p=head; q=p->next; while(q&&q->next&&p!=q) //q or q->next ==NULL时无环， q==q时有环 { p=p->next; q=q->next->next; } if(p==q) cout<<"have ring"; else cout<<"no ring";

【 在 bullet 的大作中提到: 】 : 2.如果没环的话最后结点p->next = NULL,否则p->next != NULL,让两个指针从头结点开始，以不同速度遍历，如果有环，两个指针会相等。 : 假如头结点为link * head. : link * p,*q; : ................... 经典.谢谢

【 在 bullet 的大作中提到: 】 : 2.如果没环的话最后结点p->next = NULL,否则p->next != NULL,让两个指针从头结点开始，以不同速度遍历，如果有环，两个指针会相等。 : 假如头结点为link * head. : link * p,*q; : ................... 这解法的基本原理是： 步长分别为1和2进行同速度遍历，如果环存在的话某一时刻两者存在同一节点。 昨晚闲的蛋疼，觉得知其然也要知其所以然，所以就把这个原理自己证明了一下，现在写上让大家共享:) 这个题重新描述为 在环内遍历m步以后，是否可能相交。也就是要验证m是否存在。验证m存在，就要证明m>0且m为整数。 现假设进行m步以后，在环内相交： 则： [t+2(m-1)]%n = [t+m-1]%n = d 其中t为单链起始环的节点，n为环的个数，d为相遇的节点。 故： t+2(m-1) = N1*n+d (1) t+m-1 = N2*n+d (2) (2) - (1)得： m = (N1-N2)n + 1 当m大于某个整数时, N1 > N2，故 m > 0 且为整数。所以m存在。 也就是原理得征.

谢谢啦,证明才是精髓. 【 在 jmpesp 的大作中提到: 】 : 这解法的基本原理是： 步长分别为1和2进行同速度遍历，如果环存在的话某一时刻两者存在同一节点。 : 昨晚闲的蛋疼，觉得知其然也要知其所以然，所以就把这个原理自己证明了一下，现在写上让大家共享:) : [color=#00008B]这个题重新描述为 在环内遍历m步以后，是否可能相交。也就是要验证m是否存在。验证m存在，就要证明m>0且m为整数。 : ...................

太赞了， 但是我想可以提升速度。 哈希已经访问的节点的地址，不知道这样如何？ 【 在 jmpesp 的大作中提到: 】 : 这解法的基本原理是： 步长分别为1和2进行同速度遍历，如果环存在的话某一时刻两者存在同一节点。 : 昨晚闲的蛋疼，觉得知其然也要知其所以然，所以就把这个原理自己证明了一下，现在写上让大家共享:) : [color=#00008B]这个题重新描述为 在环内遍历m步以后，是否可能相交。也就是要验证m是否存在。验证m存在，就要证明m>0且m为整数。 : ...................

嗯 这样是最快的 【 在 shuwn 的大作中提到: 】 : 太赞了， : 但是我想可以提升速度。 : 哈希已经访问的节点的地址，不知道这样如何？

static成员函数在编译时候就有了地址吧 【 在 yangxiao 的大作中提到: 】 : 类中 static成员函数在编译的时候和普通成员函数 有什么区别 : rt~。。。 : 完全不知道。。。 : ...................

static成员函数与具体的对象没有关系，只是和类本身相关。你可以认为是一个普通的函数，只是为了管理和使用的方便，放在一个类里面了而已。 普通的成员函数，有隐藏的this指针作为第一个参数，static成员函数，由于与对象无关，所以没有这个隐藏指针。 环的这个问题有点疑问，那多久以后就认为确实没有环了呢？莫非一直循环下去？好像只能说算法停止了，就肯定有环，但不能说算法没停止，就肯定没环啊，可能只是因为环很大而已。

【 在 ericyosho 的大作中提到: 】 : static成员函数与具体的对象没有关系，只是和类本身相关。你可以认为是一个普通的函数，只是为了管理和使用的方便，放在一个类里面了而已。 : 普通的成员函数，有隐藏的this指针作为第一个参数，static成员函数，由于与对象无关，所以没有这个隐藏指针。 : 环的这个问题有点疑问，那多久以后就认为确实没有环了呢？莫非一直循环下去？好像只能说算法停止了，就肯定有环，但不能说算法没停止，就肯定没环啊，可能只是因为环很大而已。 2.算法是肯定会停止的呀，1楼已经给出了代码^ ^。 5楼说可以hash地址，这个似乎更妙，自己写个hash函数，如果有冲突就肯定有环。