Home > Mobile >  Difference in a C pointer behavior when incremented in the for loop definition vs inside for loop
Difference in a C pointer behavior when incremented in the for loop definition vs inside for loop

Time:01-22

I'm onto a leetcode problem (Floyd’s Cycle Detection Algorithm for Linked List) wherein I noticed a strange behavior on the pointer states. When I change the pointer state inside the for loop, the program executes correctly (pointer states move to the right states):

ListNode *detectCycle(ListNode *head) {
        
        if(!head or !head->next)
            return nullptr;
        
        ListNode *slow, *fast;
        
        for(slow = head, fast = head; fast && fast->next;)
        {
            slow = slow->next, fast = fast->next->next; // This hops the pointers correctly

            if(slow == fast)
            {
                slow = head;
                while(slow != fast)
                {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }

But when I state change slow & fast in the for loop definition, the state change is wrong and the program doesnt give the right output.

ListNode *detectCycle(ListNode *head) {
        
        if(!head or !head->next)
            return nullptr;
        
        ListNode* slow, *fast;
        
        for(slow = head, fast = head; fast && fast->next; slow = slow->next, fast=fast->next->next) // Pointers dont hop correctly
        {
            if(slow == fast)
            {
                slow = head;
                while(slow != fast)
                {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }

I dont know whats causing this. In my head, incrementing the pointers in the for loop definition vs immediately in the for loop should be the same thing. Can someone throw an insight as to why incrementing pointers within the loop vs in the for loop signature leads to different behavior?

CodePudding user response:

A

for (init-statement; condition; iteration-expression)
{
    dostuff();
}

maps to

{
    init-statement
    while ( condition ) 
    {
        dostuff();
        iteration-expression ;
    }
}

so we get

{
    slow = head, fast = head;
    while (fast && fast->next)
    {
        slow = slow->next, fast = fast->next->next; 
        dostuff(); // for example purposes only. Not really replacible with a function 
    }
}

and

{
    slow = head, fast = head;
    while (fast && fast->next)
    {
        dostuff();
        slow = slow->next, fast=fast->next->next;
     }
}

In the first, slow and fast are always updated before dostuff().

In the second, dostuff happens before slow and fast are updated, so the values of slow and fast used in dostuff will be different on the first loop iteration.

  •  Tags:  
  • Related