单链表有环问题随记

针对面试中遇到的问到的单链表的问题，这里做一个简单的记录。

针对单项链表出现的面试问题，可能涉及一下三个方面

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.两个单链表如果相交，那么，两个单链表是否有环的特性形同。