My concern about getting rid of loop from single link list

Question

I know it is a FAQ and have a lot of answers such as Interview: Remove Loop in linked list - Java. but I have the following concerns. If I am wrong, please point out and would you please direct me to a link with right answer?

If want to not only detect but also remove the cycle, should change if (fast_ptr==slow_ptr || fast_ptr->_next == slow_ptr) to if (fast_ptr==slow_ptr) ; because there is only one entrance point.
Should consider the case when entrance if head. i.e. the case: 1->2->3->4->1->2->3->4..., I never see any link show this case. Am I wrong?

Here is my code:

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;    
}

score 0 · Answer 1 · answered May 08 '13 at 04:27

0

Start with slowptr = head, fastptr = head->next. Do the two compares before updating slowptr and fastptr.

You don't want to remove the check, as you say in 1). When (fastptr == slowptr || fastptr->next == slowptr), you have the cycle, as you understand. Removing the cycle is simply a matter of changing whichever is pointing to slowptr to point to null. You don't need a special case for (tail->next == head) -- try it.

The second loop is redundant and will never break.

To reiterate (no pun intended), to break the cycle, you change

answered May 08 '13 at 04:27

Ben Brammer

988
4
11

Hi, Ben, Thannks for your answer. I just updated my original post since I found the code is a little different from what I tested. – user389955 May 09 '13 at 04:55
Hi, Ben, Thanks for your answer. I just updated my original post since I found the code is a little different from what I tested. I also posted the code according to what you mean (see below): 1)fastptr = head->next. 2)check fastptr->next == slowptr as well. 3) remove the code which checks the special case in which tail->next=hd. But I found in this case,slow ptr will eventually stop at 3 (step of slow:1,2,3, fast=2,4,2)so by breaking slow->next=null, the link list becomes: hd=1->2->3->null, not 1->2->3->4->null,4 is missed; while w. above code, the loop breaks after 4:1->2->3->4->null. – user389955 May 09 '13 at 05:10

score 0 · Answer 2 · answered May 09 '13 at 04:53

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;
}

My concern about getting rid of loop from single link list

2 Answers2