知不知

bool IsExitsLoop(List *head){
   List *slow = head, *fast = head;
    
   while ( fast && fast->next ){
       slow = slow->next;
       fast = fast->next->next;
       if ( slow == fast ) break;
   }
    
   return !(fast == NULL || fast->next == NULL);
}

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：
    
2s = s + nr
s= nr
    
设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
    
(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。程序描述如下：
    
list* FindLoopNode(list* head){
   list *slow = head, *fast = head;
    
   while ( fast && fast->next ){
       slow = slow->next;
       fast = fast->next->next;    //fast每次两步，slow每次一步
       if ( slow == fast ) break;  //当两指针相等时，判断链表中有环
   }
    
   if (fast == NULL || fast->next == NULL) //没有环就返回
       return NULL;
    
   slow = head;
   while (slow != fast){   //一个头指针，一个相遇点指针，两个第一次相等时为环入口点
        slow = slow->next;
        fast = fast->next;
   }
    
   return slow;
}

struct Node{  
   int value;  
   Node * next;  
};  
 
//1.先判断带不带环  
//判断是否有环，返回bool，如果有环，返回环里的节点  
//思路：用两个指针，一个指针步长为1，一个指针步长为2，判断链表是否有环  
bool isCircle(Node * head, Node *& circleNode, Node *& lastNode){  
   Node * fast = head->next;  
   Node * slow = head;  
   while(fast != slow && fast && slow){  
       if(fast->next != NULL)  
           fast = fast->next;  
       if(fast->next == NULL)  
           lastNode = fast;  
       if(slow->next == NULL)  
           lastNode = slow;  
       fast = fast->next;  
       slow = slow->next;     
   }  
   if(fast == slow && fast && slow){  
       circleNode = fast;  
       return true;  
   }  
   else  
       return false;  
}  

//判断带环不带环时链表是否相交  
//2.如果都不带环，就判断尾节点是否相等  
//3.如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。  
bool detect(Node * head1, Node * head2){  
   Node * circleNode1;  
   Node * circleNode2;  
   Node * lastNode1;  
   Node * lastNode2;  
     
   bool isCircle1 = isCircle(head1,circleNode1, lastNode1);  
   bool isCircle2 = isCircle(head2,circleNode2, lastNode2);  
     
   //一个有环，一个无环  
   if(isCircle1 != isCircle2){  
       return false;  
   //两个都无环，判断最后一个节点是否相等  
   }else if(!isCircle1 && !isCircle2){  
       return lastNode1 == lastNode2;  
   }  
   //两个都有环，判断环里的节点是否能到达另一个链表环里的节点  
   else{  
       Node * temp = circleNode1->next;   
       while(temp != circleNode1){  
           if(temp == circleNode2)  
               return true;  
           temp = temp->next;  
       }  
       return false;  
   }  
     
   return false;  
} 

struct ListNode{
   char data;
   ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;
    
   //求链表倒数第k个结点应该考虑k大于链表长度的case。
   ListNode* fun(ListNode *head,int k){
   assert(k >= 0);
   pone = ptwo = head;
   for( ; k > 0 && ptwo != NULL; k--)
       ptwo=ptwo->next;
   if (k > 0) return NULL;
    
   while(ptwo!=NULL){
       pone=pone->next;
       ptwo=ptwo->next;
   }
   return pone;
} 

//求链表的中间节点
Node* theMiddleNode(Node *head){
    if(head == NULL)
        return NULL;
    Node *slow,*fast;
    slow = fast = head;
    //如果要求在链表长度为偶数的情况下，返回中间两个节点的第一个，可以用下面的循环条件
    //while(fast && fast->next != NULL && fast->next->next != NULL)  
    while(fast != NULL && fast->next != NULL){
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

//单链表的转置,循环方法
Node* reverseByLoop(Node *head){
    if(head == NULL || head->next == NULL)
        return head;
    Node *pre = NULL;
    Node *next = NULL;
    while(head != NULL){
        next = head->next;

        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

//单链表的转置,递归方法
Node* reverseByRecursion(Node *head){
    //第一个条件是判断异常，第二个条件是结束判断
    if(head == NULL || head->next == NULL) 
        return head;

    Node *newHead = reverseByRecursion(head->next);

    head->next->next = head;
    head->next = NULL;

    return newHead;    //返回新链表的头指针
}