面试题系列
大概的题意是，给出一个单向链表的头节点，求这么链表是否有环。有环的定义是，链表的尾节点指向了链接中间的某个节点。单链表的定义如下：
1 2 3 4 | struct Node { Node(): next(NULL) {} Node *next; }; |
这道题目还有一些变种，比如求链接的长度，求链表的尾节点等，不过大同小异。第一次听说这个题目，是在大三的时候，从一个刚面完试的学长那里。他当时的做法是对这个链表求逆，求逆的结果链表上每一个指针都反向，如果逆序完之后，链表的头节点不变，即说明链接有环。具体的证明过程略。这个方法的复杂也是O(N)，但是需要修改原链表，或者使用O(N)的额外空间。