1.判断单链表是否带环？若带环，求环的长度？求环的入口点？并计算每个算法的时间复杂度&空间复杂度

思路：还是通过快慢指针来解决，让fast指针每次走2个结点，慢指针一次走一个结点

时间复杂度为O(n)   空间复杂度O(1 )

注意：fast每次走3个 4个.. 结点是不行的。分析如下：

 

考虑清楚后，便可以写下代码：

//（1）判断链表是否带环
SListNode* SListIsCycle(SListNode* list) { assert(list); SListNode* fast = list; SListNode* slow = list; while(fast && fast->_next){ fast = fast->_next->_next; slow = slow->_next; if(slow == fast){ return fast;   //返回相遇点地址 
 } } return NULL; }


（2）求环长度 
思路如下：
把相遇点的下一个结点地址赋给cur ，cur按环遍历一圈，通过计算器count便可求得环长
时间复杂度O（n） 空间复杂度O（1）
int SListCycleLen(SListNode* meetNode){ assert(meetNode); size_t count = 0; SListNode* cur = meetNode->_next; while(cur != meetNode){ count++; cur = cur->_next; } return count+1; } 

（3） 求入口点

 

如果说不太理解“slow和fast第一次相遇，slow没绕环走超过一圈”。可以考虑这样一种情况：

注：slow和fast同时从一个地方走，这种情况下它们之间相差距离是最大的（刚好一圈）。v(fast) = 2v(slow), fast先进入环内。

 

有了以上分析，不难写得如下代码：

//meet的下一个结点地址赋给cur，list，cur同时往后走，相遇点即是入口点
时间复杂度O（n） 空间复杂度O（1）

SListNode* SListEntryNode(SListNode* list, SListNode* meetNode) {
    assert(list && meetNode);
    
    SListNode* cur = meetNode;
    while(cur != list){
        cur = cur->_next;
        list = list->_next;
    }
    return cur;
}

 

2.判断两个链表是否相交，若相交，求交点。（假设链表不带环）

 

思路：
1.先遍历两链表求得长度分别为x1,x2; 2.让指向长链表的指针先走|x1 - x2|的长度 3.最后两指针同时走，直到相遇 

SListNode* SListNonCircleIsCrossNode(SListNode* list1, SListNode* list2){
    assert(list1 && list2);
    
    size_t x1 = 0,x2 = 0;
    SListNode* cur1 = list1; //注意定义中间变量来遍历，list1、list2是两链表的头指针，不能改变其指向，故不能用来遍历， SListNode* cur2 = list2; while(cur1){
        cur1 = cur1->_next;
        x1++;
    } 
    while(cur2){
        cur2 = cur2->_next;
        x2++;
    }
    
    SListNode* longList = list1;
    SListNode* shortList = list2;
    if(x2 > x1){
        longList = list2;
        shortList = list1;
    }
    int gap = abs(x1 - x2);  //abs() 调用求绝对值函数 
    while(gap--){
        longList = longList->_next;
    } 
    //两指针同时走
    while(longList){
        longList = longList->_next;
        shortList = shortList->_next;
        if(longList == shortList){
            return longList;     //返回交点地址 
        }
    } 
    return NULL;
} 

3.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】

需分下面几种情况讨论：
 （1）都不带环，转换成2题。  
 （2）一个带环，一个不带环。那一定不相交（若相交了，原链表结构肯定被改变了）。  
 （3）都带环。都带环也分为以下三种情况（利用两个相遇点(M1,M2) 判断是否带环——让M1不动，M2走一圈，如果两个能相遇，那就相交，反之不相交）  
  ①不相交 

从meet遍历一遍环，能找到meet2则判定两环是相交

 ②环外相交（入口点相同）——从入口点处把链表截断，问题就转换成求两个不带环链表相交点。 
 

            

 ③环内相交（入口点不同）
 

 

SListNode* SListCrossNode(SListNode* list1, SListNode* list2){
    assert(list1 && list2);
    //情况①：都不带环，转到上题 
    if(!SListIsCycle(list1) && !SListIsCycle(list2)){
        SListNonCircleIsCrossNode(list1,list2);
    }
    
    //情况②：都带环 
    else if(SListIsCycle(list1) && SListIsCycle(list2)){
        SListNode* pMeetNode1 = SListIsCycle(list1);  //上题函数 
        SListNode* pMeetNode2 = SListIsCycle(list2);     
        SListNode* cur = pMeetNode1->_next;
        
        while(cur != pMeetNode1 || pMeetNode1 == pMeetNode2){
            if(cur == pMeetNode2){ //相交的情况
                SListNode* entry1 = SListEntryNode(list1, pMeetNode1); //返回list1入口点 
                SListNode* entry2 = SListEntryNode(list2, pMeetNode2); //返回list2入口点 
                
                if(entry1 == entry2){   //两入口点相同，环外相交 
                    entry1->_next = NULL;
                    return SListNonCircleIsCrossNode(list1 , list2);
                }
            
                
                else{                //两入口点不同，环内相交 
                    printf("有两个交点，分别就是两个入口点\n");
                    int n = 0;
                    scanf("%d",&a