0

私はそれがFAQであることを知っており、インタビュー：リンクされたリストのループを削除する - 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;    
}
4

2 に答える 2

0 
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;
}
于 2013-05-09T04:53:36.117 に答える
0

slowptr = head、fastptr = head->next で開始します。slowptr と fastptr を更新する前に、2 つの比較を行います。

1) で述べたように、チェックを外したくありません。(fastptr == slowptr || fastptr->next == slowptr) の場合、ご理解のとおり、サイクルがあります。サイクルを削除するには、slowptr を指しているものを null に変更するだけです。(tail->next == head) の特別なケースは必要ありません -- 試してみてください。

2 番目のループは冗長であり、壊れることはありません。

繰り返しますが (しゃれは意図していません)、サイクルを断ち切るために、あなたは変わります

于 2013-05-08T04:27:38.397 に答える