针对面试中遇到的问到的单链表的问题，这里做一个简单的记录。
针对单项链表出现的面试问题，可能涉及一下三个方面
1.链表是否环；
2.链表的环入口
3.有环链表的结点长度
4.两个链表是否相交
针对前三个问题，一种容易想到的是通过遍历链表，将遍历过的结点进行记录，新的遍历结点和记录结点是否有相等，如果出现，证明链表有环，链表的环入口就是相同结点处，环链表的长度就是记录的长度。
一、给定一个链表是否有环问题
快慢指针的方法。
定义两个指针slow，fast，slow指针每次向前移动一个节点，fast指正每次向前移动两次指针。如果出现fast==slow的现象，则证明有环，否则证明没有环；
bool has_cycle(LNode* lhead){
bool result = NO;
LNode * fast = lhead ;
LNode * slow = lhead;
while (fast && fast->next) {
slow = slow->next;
fast = ((LNode *)(fast->next))->next;
if (slow == fast) {
result = YES;
break ;
}
}
return result;
}
复杂度：时间复杂度为：n；空间复杂度为：1。
二、环入口
当通过快慢指针的方法，确定链表有环的时候。当假设环入口在p结点出现，快慢指针重逢在距离p点为c的结点上面。
可以得到：
m = p + c;
2m = p + c + kL;
其中，m为慢指针走的步数，2m为快指针走的步数，k为正整数，L为环长度，其中链表的长度等于：p + L;
有此可以得到: p + c = kL， p = kL - c；
如果此时将快指针回退到head处，flow和slow指针同时以每次一步向前走的话，那么最后当指针重新回到p点处是，慢指针距离第一次重逢点的距离恰好是c，即也是p点，所以第二次重逢处恰好就是环入口处。
LNode * fine_lineCyclePort(LNode * lhead){
LNode * result = NULL;
bool has_cycle = NO;
LNode * fast = lhead ;
LNode * slow = lhead;
while (fast && fast->next) {
slow = slow->next;
fast = ((LNode *)(fast->next))->next;
if (slow == fast) {
has_cycle = YES; //第一重逢，证明链表有环。
break ;
}
}
if (has_cycle) {
//有环的情况下
fast = lhead;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
result = fast; //第二次重逢，重逢点为有环链表的入口点。
}
return result;
}
复杂度：空间复杂度为：1，空间复杂度为：m+p = 2p + c = kL +p = (k-1)L + n,n为链表长度，所以时间复杂度为n。
三、链表的长度。
通过上面获得链表的环入口后，可以通过，重新遍历链表，当第二次出现，于p处指针相同的时候，之前的比较次数就是链表的长度。
四、两个单链表是否相交
两个链表如果相交，具有以下两种特征：
1.两个单链表只可能出现Y型相交，不可能出现X型相交。
2.两个单链表如果相交，那么，两个单链表是否有环的特性形同。
