MERGE SORT IN LINKEDLIST

#1

KINDLY EXPLAIN THE TIME AND SPACE COMPLEXITY OF THIS.

#2

hello @CODER_JATIN

time complexity will remain o(nlogn)
becuase recurrence relation will rmain same.
t(n)= 2* t(n/2) + c*O(n)

space complexity will be O(logn) becuase height of recursive tree will be log(n) and no other extra space will be consumed

#3

https://ide.codingblocks.com/s/410337 , kindly check this function , why it is not giving desired results?

#4

pls share ur complete code.

#5

https://ide.codingblocks.com/s/410343 , this is my complete code, pls consider mergesort() function for my query?

#6 
node*middle(node*head)
{
    node*fast=head;
    node*slow=head->next;//update

    while(fast!=NULL && fast->next!=NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
    }

    return slow;
}
#7

but in middle function , both slow and fast pointer should be at same point initially, and why are you taking slow=head->next; ???

#8

to avoid infinite recursion .

dry run for list with 2 nodes. the previous program will stuck in infinite recursion

#9

Hanji bhaiya 2 node ke liye infinite recursion ho jaayega, lekin jab ham agar slow=head->next krte hai to mid fir NULL to point krega tab bhi segmentation fault aajega

#10

sry wo ulta likh diya uppar,
fast ko head ->next karna hai aur
slow=head;

#11

bhaiya vese dekha jaaye to head or slow dono ek hi point pe point krne chahiye initially tabhi to usko bolenge two pointer runner technique , to yeh cheez to hamey ese har question mai yaad rkhni pdegi?

#12

nahi ye bhi runner technique hi hein, bus fast ko thoda modify kiya hein.

nahi ds-algo mein kuch yaad ya ratta nahi maarna bus samajh jo aisa kyun kiya , wo dimag mein hamesha rahega

#13

OKay bhaiya ji , thank you.

#14

bhaiya linkedlist merge sort agar without recursion karna hoga to kese karenge?

#15

first solve merge sort for array iteratively.

and then for linkedlist.

here is the approach ->link

#16

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.