Reorder list problem

#1

i was trying the following problem: https://leetcode.com/problems/reorder-list/

and was getting unexpected result.below is my code: https://ide.codingblocks.com/s/574921

i couldnt get the bug in my code…pls help

#2

Modified Code

ListNode* reverse(ListNode* head){
         if(!head or !head->next) return head;
         ListNode* dummy=reverse(head->next);
         head->next->next=head;
         head->next=NULL;
         return dummy;
    }
    
void reorderList(ListNode* head) {
        if(!head or !head->next) return;
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast and fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        slow->next=reverse(slow->next);
        fast=slow->next;
        slow->next=NULL;// this condition should be added to avoid cycle formation
        slow=head;
        while(fast!=NULL){
            ListNode* temp1=slow->next;
            ListNode* temp2=fast->next;
            slow->next=fast;
            fast->next=temp1;
            slow=temp1;
            fast=temp2;
        }
    }

actually you are going into a loop
because cycle is formed in your code

i have commented that line
now it passes all test case

#3

Sir can you pls elaborate how a cycle is formed without adding slow->next=NULL;

#4

dry run your code for this input

1 2 3 4 5 6 7

you will understand it very well

#5

sir, i tried dry running before also on same sample…
after reversing we got 1 2 3 4 7 6 5…our fast pointer is now on 7 and slow is on 1.
when we are running the while loop we are checking on fast pointer and it becomes null after 7 6 5…
and here we dont have to look at slow…so loop should terminate but not… so now where the problem is occuring…

#6

when fast is on 7 and slow is no 1

also consider that list is not broken
4 still points to 7
so when 7 comes after 1 then list will look like this

image
image1218×740 50 KB

so that list broke into 2 parts

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.