c - 我担心从单链接列表中摆脱循环

Question

我知道这是一个常见问题解答，并且有很多答案，例如Interview: Remove Loop in linked list - Java。但我有以下担忧。如果我错了，请指出，你能指导我到一个正确答案的链接吗？

1. 如果既要检测又要清除循环，应更改if (fast_ptr==slow_ptr || fast_ptr->_next == slow_ptr)为if (fast_ptr==slow_ptr); 因为只有一个入口点。
2. 入口时应考虑头部情况。即案例：1->2->3->4->1->2->3->4...，我从来没有看到任何链接显示这种情况。我错了吗？

这是我的代码：

bool determine_remove_Cycle_list(sIntElement *head){     
    sIntElement* slow_ptr = head;    
    sIntElement* fast_ptr = head;     
    while(true){    
        if (!fast_ptr || !(fast_ptr->_next)) return false;     
        slow_ptr = slow_ptr->_next;    
        fast_ptr = fast_ptr->_next->_next;    
        if (fast_ptr==slow_ptr)//fast_ptr->_next == slow_ptr is not checked
            break; //is cycle
        }
        fast_ptr = head;    
        while(fast_ptr->_next != slow_ptr->_next){    
            fast_ptr = fast_ptr->_next;    
            slow_ptr = slow_ptr->_next;    
        }    
     }
     if (slow_ptr == head){ //special case: start of the cycle is head,    
            while (slow_ptr->_next != head){    
            slow_ptr = slow_ptr->_next;    
     }    

     slow_ptr->_next = NULL; //slow is the node before the start point
     return true;    
}

Answer 1

从 slowptr = head 开始，fastptr = head->next。在更新 slowptr 和 fastptr 之前进行这两个比较。

正如您在 1) 中所说，您不想删除支票。当 (fastptr == slowptr || fastptr->next == slowptr) 时，如您所知，您有循环。删除循环只是将指向 slowptr 的任何一个更改为指向 null 的问题。您不需要 (tail->next == head) 的特殊情况——试试吧。

第二个循环是多余的，永远不会中断。

重申（不是双关语），打破循环，你改变

Answer 2

bool determine_remove_Cycle_list_2(sIntElement *head){ 
    sIntElement* slow_ptr = head;
    if (!head) return false;
    sIntElement* fast_ptr = head->_next; 
    while(true){
       if (!fast_ptr || !(fast_ptr->_next)) return false; 
       if (fast_ptr==slow_ptr || fast_ptr->_next == slow_ptr)
            break; //find the cycle
       else {
        slow_ptr = slow_ptr->_next;
        fast_ptr = fast_ptr->_next->_next;
       }
    }  
//slow is at position p here.
    fast_ptr = head;

    while(fast_ptr->_next != slow_ptr->_next){
    fast_ptr = fast_ptr->_next;
    slow_ptr = slow_ptr->_next;
    }

    slow_ptr->_next = NULL; 
    return true;
}