Flattening of a Linked List | Amazon | Microsoft
Вставка
- Опубліковано 9 лют 2025
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUfo...) ..
✅Entire Series: bit.ly/placemen...
✅Problem link: practice.geeks...
✅Unacademy has launched a subscription that will help you learn and interact with your favorite teacher and will also help you clear your doubts! Check it out here: unacademy.com/.... (use coupon code TAKEUFORWARD to get 10% off)
Free Classes Links
Beginners Classes - unacademy.com/...
Intermediate Classes - unacademy.com/...
Advanced Classes - unacademy.com/...
Test Link :- unacademy.com/...
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_...
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgC...
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competiti... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements
C++ code: github.com/striver79/SDESheet/blob/main/flatteningOfLinkedListCPP
Java code: github.com/striver79/SDESheet/blob/main/flatteningOfLinkedListJava
For live sessions, follow at Insta: instagram.com/striver_79/
The TC of optimal approach will be (2x + 3x + 4x + 5x + ..... kx) assuming the single linkedlist to be of size x on average. We cannot use min heap here because, we want to change the current LinkedList pointers. So thinking of min heap is not a good idea because you need to flatten the linkedlist only!
We can use the divide and conquer approach. TC will be - O(N*X*log(N))
Hi brother, Can you explain the TC, which u mentioned in comment? I think TC would be O((num_of_nodes)^2)
@Gourav Sharma cs21m020 If given linked has n straight nodes and each has m childrens, I think time comlexity will be O(n^2*m). Correct me If I'm wrong. I think time complexity analysis is more important in this question.
hi, correct me if im wrong but doesn't the time complexity mentioned make the algo very inefficient(TLE over 1e5)? Should we use something like n pointers and apply 2 pointers on them simultaneously?
Ig Pairwise Merge Approach is better...
TC: O(MN*logN) or O(total_nodes * log N), Assuming N lists each of max M nodes per list.
Node* sortTwoLists(Node* first, Node* second)
{
if(!first || !second)
return (first ? first : second);
first->next = second->next = NULL;
Node *nh=NULL, *nt=NULL;
if(first->data data)
nt=nh=first;
else
nt=nh=second;
while(first && second){
if(first->data data){
if(nt != first){
nt->child = first;
nt = nt->child;
}
first = first->child;
}
else{
if (nt != second) {
nt->child = second;
nt = nt->child;
}
second = second->child;
}
}
if(!first){
nt->child = second;
}
if(!second){
nt->child = first;
}
return nh;
}
Node* flattenLinkedList(Node* head)
{
while(head && head->next){
Node *temp = head;
while(temp && temp->next){
Node *next = temp->next->next;
temp = sortTwoLists(temp, temp->next);
temp->next = next;
temp = next;
}
}
return head;
}
*Correct Time complexity* :
If we consider each vertical linked list of size O(M) in the worst case, then in this method we are merging two vertical sub-linked lists at a time.
Time is taken to merge two linked lists of size M = O(M+M) =O(2M)
Similarly, the time is taken to merge another linked list of size M with a linked list of size 2M = O(M+2M)=O(3M)
Similarly, the time is taken to merge another linked list of size M with a linked list of size 3M = O(M+3M) =O(4M).
This process will take place N times where N is the no of nodes in the horizontal linked list. So, the total time taken till all the nodes are merged = O(2M+3M+4M+5M+...N * M )
= O(2+3+4+5+6...+N)* M
=O(N* ( N + 1 ) / 2)* M
= O(N * N * M)
yes you are right
Without recursion -
Node* Flatten(root)
{
While(root && root->next)
{
Node* temp = root->next->next;
root = merge(root, root->next);
root->next = temp;
}
Return root;
}
This approach is way more intuitive , thanks for sharing.
Simple c++ code
// TC - O(n2), SC - O(1)
Node *flatten(Node *root)
{
for(auto it=root->next; it!=NULL; it=it->next){
Node *temp=root;
for(auto t=it; t!=NULL; t=t->bottom){
while(temp->bottom){
if(temp->bottom->data>t->data){
break;
}
temp=temp->bottom;
}
Node* tmp=temp->bottom;
Node* cur=new Node(t->data);
temp->bottom= cur;
cur->bottom=tmp;
}
}
return root;
}
quality of content is simply awesome and the explanation skill is at its best! Thank You very much bro!
For those who find this though, just look my approach with O(total node) and o(1) space
without recursion...
NOTE : i hope u have done merging of two sorted linked list from leeetcode ( easy level question )
Algo
1)point h1 =head and h2=h1.next
2)pass h1 and h2 as parameters to merge these two sublinked list into sorted list
3) update h1= mergerTwoSortedList(h1,h2);
update h2= h2.next;
4) repeat 3rd step untill h2!=null
here is the code ---->
Node flatten(Node root) {
Node h1 = root;
Node h2 = h1.next;
while (h2 != null) {
h1 = mergeTwoLists(h1, h2);
h2 = h2.next;
}
return h1;
}
// bellow question is in leetcode
Node mergeTwoLists(Node l1, Node l2) {
// l1 will always point out to smaller element LL
if (l1 == null)
return l2;
if (l2 == null)
return l1;
if (l1.data > l2.data) {
Node temp = l1;
l1 = l2;
l2 = temp;
}
Node res = l1;
while (l1 != null && l2 != null) {
Node temp = null;
while (l1 != null && l1.data
thanks bro recursion seems little bit tough to me 🥵
exactly my approach
@@gundalaavinash2438 it wotnt be deprecated
we can also start merging from the beginning , i.e. the first to nodes. the code is easy
to explain that way and the space complexity reduces.
can u send that code Thank you!!
@@ajitgupta1530 yes please
@@ajitgupta1530 Node *flatten(Node *root)
{
if(root->next==NULL)
return root;
Node* ans=sortedMerge(root,root->next);
Node* curr=root->next->next;
while(curr)
{
ans=sortedMerge(ans,curr);
curr=curr->next;
}
return ans;
}
Node* sortedMerge(Node* list1, Node* list2)
{
Node* sort;
if(list1==0)
return list2;
else if(list2==0)
return list1;
if(list1->datadata)
{
sort=list1;
list1=list1->bottom;
}
else
{
sort=list2;
list2=list2->bottom;
}
Node* FinalHead=sort;
while(list1 and list2)
{
if(list1->datadata)
{
sort->bottom=list1;
sort=sort->bottom;
list1=sort->bottom;
}
else
{
sort->bottom=list2;
sort=sort->bottom;
list2=sort->bottom;
}
}
if(list1==NULL)
{
sort->bottom=list2;
}
else
sort->bottom=list1;
return FinalHead;
}
@@sumitchakraborty9451 thanks bhhai
aage se merge karna is more easy and simple for understand
@@sumitchakraborty9451 curr=root->-next->next plz explain
I think time complexity wont be O(total nodes), This gives a better idea -
"Suppose n straight nodes and each have m chilldren.
Time would be like m + 2m + 3m + 4m ......( total nterms)
so it would be (m*n*(n+1))/2
which is m*n*n;"
src - gfg comment from Decostar kumar
In Python :
def mergedLL(a , b):
temp = Node(0)
res = temp
while a and b :
if a.data < b.data :
temp.bottom = a
a = a.bottom
temp = temp.bottom
else :
temp.bottom = b
b = b.bottom
temp = temp.bottom
if a :
temp.bottom = a
else:
temp.bottom = b
return res.bottom
def flatten(root):
if not root or not root.next :
return root
root.next = flatten(root.next)
root = mergedLL(root,root.next)
return root
1. Respected Sir , Please explain how space complexity is O(1) . We are using recursion here . And we count space complexity due to recursion call stack also . I think space complexity should be BIg O(summasion of no of nodes coonected via next pointer) .
2. Also Please explain [not in prospect of this question , i m asking generally ] , if we have a recursion call stack of with maximum number of recursive calls= k1 and hashmap/array /vector[maybe passed in recursive calls] of size k2 together at same time with recursion, then what will be space complexity . Will it be O(k1) or O(k2) or O(k1+k2)
Also thanks for making such indepth videos with detailed notes on TUF website
he is not passing the entire linked list or say an array. In this case the data gets into a huge stack. he is simply passing pointers and tracing the rest from them hence the recursion stack wont take so much space.
so the concept is: the stack space will only consist of the elements in the next pointer of root, not the elements from bottom pointers. All the elemnts from bottom pointer will be traced iteratively in merge function. All the recursive calls he makes .....are only for the nodes in the horizontal line. Comparatively, this is a small number of nodes considering the bottom nodes can be in much larger number than "next" poiter nodes. So we can assume, the total space required is wayyy less than total number of nodes because we aren't calling ALL the nodes.
@@divyareddy7622 absolutely true
UNDERSTOOD... !!!
Thanks striver for the video... :)
Thanks bro,
Your energy is authentically awesome. Keep it up and make quality content like this. Hats off bro.
For those who are not understanding why head->next will point to NULL in the answer .The reason is simple
we are making a temp node and you know when we make a object using new keyword all its properities will going to assigned to object.So basically we are returning everytime res->bottom.So res ->bottom is just temp which has next always pointing to NULL.So basically head is temp and was pointing to NULL.
really waiting for this question... very well explained bro
Was waiting bro. Happy to know you are healthy. Thanks a lot bro
very easily you explained this question thank you
As we are using recursion here. The space complexity must be O(n) which is the maximum depth of recursion tree instead of O(1). Isn't it ? BTW the way you explain each approach is really damn great !!
System uses the stack and we are not using it so space complexity is 0(1).If we use our own stack then the space complexity is 0(n).
You can use for loop also , space would be O(1) then 👍
@@watchlistsclips3196 recursion is considered in SC, unless it is Tail recursion
@@sachin__ak Makes sense
@@sachin__ak Tail recursion should also be considered in space complexity since the function call still stays inside stack.
How do you even think this way bruh, haha, thanks for the content!
Best solution ever for This question
The mergeList() function works for question - "merge 2 sorted linked lists" as well!, but performs poorly in terms of time complexity.
Excellent explanation anyways!
well, is there a better solution
@@debdhritiroy6868 there is a seperate video dedicated for that problem.
my fav teacher.
Your content is the best! I am immensely grateful to you!!
Thank you so much Striver Sir , working this hard that too selflessley makes you more than what you already are. You deserve a huge round of applause.
Thank You.
😀
Awesome explanation!!
u made it so simple to understand! cool. thanks indeed!
nice explanation Striver you are the best .. take love
understood, thanks for the great explanation
recursive soln: 9:30
cpp soln: 16:00
Thank you
quality content bro, keep it up
Iterative solution in python
def mergeTwoLists(list1,list2):
temp1,temp2 = list1,list2
res = Node(0)
temp3 = res
while(temp1 and temp2):
if temp1.data
awesome explanation bhai❤
Maza aa gya😭😭❤.। Thankyou striver
Thanks Striver!!
bapre..jstttt awesome yarr ❤️
so Precise and easy to understand explanation ! Thanks bhaiya ❤️
Thanks for all the effort
Thanks for such a great explanation.
Thank you so much for making this video.. Really helped a lot😃
Nice explanation your videos are really good...keep making such videos.
Doing the same thing using loop instead of recursion will be a more optimised approach in terms of space complexity
Getting TLE in codingninjas
Thanks for your wonderful content. I have a question on TC. It should not be summation of all nodes right ?
Say for example, for list are there and each has 5 nodes....so, we are not only visiting them once but more than one time... When two last lists are merged , it becomes 10 nodes which again got compared with third list and so on
yes exactly , i was wondering about that too.
Great Explanation!
You make it easy
Super Helpfull! Thanks!
Will this really change it into flat ......? Or just printing in that way...
Please tell the optimized approach
Amazing explanation
got it understood thanks
This worked for me. Is this correct approach ?
Node *flatten(Node *root)
{
Node* temp=root->next;
Node* ans=root;
while(temp!=NULL)
{
ans=merge(ans,temp);
temp=temp->next;
}
return ans;
}
The merge function merges two sorted linked lists.
It gets accepted then yes. There are mutiple approaches to a problem..
@@takeUforward Yes Thank you
Can we use merge sort in top linked list..? Like breaking top linked in binary tree and then merge them
@@takeUforward bhaiya can we do it like that...find mid of upper linked list divide it and then merge it...
Yes i too did in the same way & it got accepted,but in this one we need to set next of node as null too,also i think iterative is more efficient bcoz recursion call stack space is not used
Thank you so much! Really helped a lot!
16:00 : C++ Code
Really helped a lot😃
I got this exact same question today
very well explained,thank you
Thank you bhai ... For your great efforts : ) ❣️
Won't the time complexity be O(N^2)?
Thanks
great explaination. Thanks
Python Solution :
def merge(a, b):
temp = Node(0)
head = temp
while a and b:
if a.data
LinkedList are real fun!
Time complexity if not O(n) guys, see you are traversing nodes again again
Great explanation!!!
ur videos are really helpful :)
" The flattened list will be printed using the bottom pointer instead of the next pointer . " wasted 1 hour because i didn't read this. God damn it. After striver read this i paused the video in frustration and solved the problem in an instant. And this code is much smaller i don't know why people complicate it. This is my code with O(n) time and O(1) space
Node flatten(Node root)
{
Node root1=root;
Node root2=root1.next;
while(root2!=null)
{
Node root3=root2.next;
Node down1=root1.bottom;
Node down2=root2;
while(down1!=null && down2!=null)
{
if(down1.data
Brilliant explanation 🙏
Prerequisites:Merge 2 sorted linked list
Thanks a lot for all your efforts bhaiya :)
Is the time complexity that you mentioned in the video correct ? let's say there are N lists in total... nodes in the last list will be visited N-1 times for merging (in worst case - where all the nodes present in the last linked list contain value less than any other node in the other lists)... similarly nodes in the second last list will be visited N-2 times and so on...
Read the pinner fomment !
@@takeUforward Oh, cool sorry bro... I didn't see that comment earlier...
@@takeUforward which pinned comment are you taking about there's no pinned comment
@@neilchaudhary007 there is, the one in which code is there
Why we are not merging head on but from the back, any reason as such, I mean iterate till we don't get the last node?
Thank you for the video :), I have one question instead of doing recursion can't we start merging from the beginning and keep on increasing next till it becomes null.
Try to do, the pointers will not work, since there is already something ahead of the second linked list.
@@takeUforward It worked for me. I used a while loop and Merged from the beginning and kept on increasing next till became NULL.
@@adhithyakarthikeyan1040 great, paste the code, it will help others.. i did not actually get clarity on your solution may be.
@@takeUforward
// This code worked for me, TC=O(N*M) and SC=O(N)
Node *flatten(Node *root) {
// Inserting all the top nodes (i.e head of each linked list) into a vector
vector arr;
Node* temp = root;
while(temp!=NULL) {
arr.push_back(temp);
temp = temp->next;
}
// Initializing a dummy node
Node* ans = new Node(-1);
Node* curr = ans;
while(1) {
// Checking if all the nodes in the vector is NULL
bool allNull = true;
for(Node* x: arr) {
if(x != NULL) {
allNull = false;
break;
}
}
// If all are NULL, no need to do anything
if(allNull) break;
// Finding the smallest node in the vector, please keep in mind to skip the NULLs
int ind = -1;
for(int i=0; idata > arr[i]->data ) {
ind = i;
}
}
// Attaching the smallest node found with our answer
curr->bottom = arr[ind];
arr[ind] = arr[ind]->bottom;
curr = curr->bottom;
}
return ans->bottom;
}
@@adhithyakarthikeyan1040 DIDN'T WORK FOR ME, only recursion is working;
Now this is what we called clean code.
Super explanation bro.
Thanks.
Great work brother ❤️
Thanks for making such amazing videos and motivating us.
Thankyou bhaiya but please increase the frequency of uploading videos.
Bro was unwell for some days, updated that on Insta :)
Hey sir. Thank you for the video.
I have a doubt, this code gets only partially accepted on the coding ninja platform.
And also sir please explain how SC will turn out to be O(1) when we are using recursion?
Same, i have this doubt too!
Did the solution got accepted?Mine is giving partially accepted too.
@@ayushidalal5488 Did the solution got accepted?Mine is giving partially accepted too.
Time Complexity: O(N*N*M) - where N is the no of nodes in main linked list (reachable using right pointer) and M is the no of node in a single sub linked list (reachable using down pointer).
I think you have pointed it out wrong Bhaiya
Please check it out once
Reason:
There would be N function calls - since each function call reduces the horizontal linked list by 1, you would need N function calls to flatten it completely.
In each function call, you are merging two sub linked lists, by traversing them linearly. The sizes of the 2 sub linked lists being merged will be -
M & M
M & 2M
M & 3M
....
M & (N-1)*M
So O(2M + 3M + ... + N*M) = O(M*N^2) = O(summation of nodes * N)
This is just amazing
Understood sir🙏
Understood Sir!
Can anyone explain why the time complexity is O(N) ? Aren't we merging two lists, and going through the same nodes again and again to merge the new list with the 'third' list? (Even the merge sort algorithm is Nlogn, this algo seems to be N*N to me)
thinking same
can we do this question without recursion?
C++ code 15:59
Thank you striver bhaiya
Hey, I think the time complexity should be O(MN^2), where N is the no. of lists and M is the size of each individual list. Intuition behind it is that the lists being merged keeps growing by M after each call. So T(N)=2M + 3M +..+ NM = O(MN^2) . Where am I wrong?
Read the pinned comment..
@@takeUforward Sry😅 didn't see that. Thanks!
I think time Complexity is wrong!!! it should be O(n*m)
where n is number of linklist and m = max length of linklist
Yes mentioned in first comment
I just used a heap
cant we just add it to an array and sort?
1:03 pe aapki gf ka message aaya and aapne 1:30 pe pause leke usko padha!
kya likha tha?
P.S: 4:20 pe door knock hua(vo ghar aa gayi)
❤
Merging last two list costs 2m operations
now these 2m nodes will be added to m nodes before it so it is 2m+m =3m
for nth operation =n*m
total time will be 2m+3m+...nm = n*n*m
am i ryt?
BTW you sheet is great and explainations too, but i feel something is wrong with this question on gfg with timecomplexity
Yeah, I thought the similar. isn't it O((n+m)^2) in the worst case? Think of a normal linked list with all bottom as null, then according to u, TC will be 0.
We are solving this recursively so , why this solution don't have exponential time complexity?
I think it is similar to k-merge sorted linked list so why its complexity is 0(n*m) but k-merge sorted has 0(n*mlog(n*m))
Here's a Iterative Soln ::
Node* mergeList(Node* a,Node *b){
Node* head = new Node(0);
Node* last = head;
while(a && b){
if(a->data data){
last->bottom = a;
a = a->bottom;
}else{
last->bottom = b;
b = b->bottom;
}
last = last->bottom;
}
last->bottom = a ? a : b;
return head->bottom;
}
Node *flatten(Node *root){
if(!root->next)
return root;
Node *f = root,*s = root->next,*nex = root->next->next;
while(s){
f->next = NULL;
s->next = NULL;
Node* m = mergeList(f,s);
f = m;
s = nex;
if(nex)
nex = nex->next;
}
return f;
}
Is space complexity would be O(N) or O(1)?
@@SjParthi O(1) no recursion involved no auxillary space required.
Thank you so much
Is it moving front to back or to front
i discovered an easy Approach:
/*
Algorithm:
Start form the head , move one step each time to the next node
When meet with a node with child, say node p, follow its child chain to the end and connect the tail node with p.next, by doing this we merged the child chain back to the main thread
Return to p and proceed until find next node with child.
Repeat until reach null
keep the diag. handy
* Time: O(N), Space: O(1)
*/
class Solution
{
public:
Node *flatten(Node *head)
{
if (!head)
return head;
Node *p = head;
while (p)
{
if (!p->child)
p = p->next;
else
{
Node *temp = p->child;
while (temp->next)
temp = temp->next;
temp->next = p->next;
if (p->next) // * IMPORTANT, CONSIDER TC: [1,null,2,null,3,null] THAT IS 3 NODES CONNECTED VERTICALLY WITH NEXT NULL FOR ALL
p->next->prev = temp;
p->child->prev = p;
p->next = p->child;
p->child = nullptr;
}
}
return head;
}
};
Bhay tu bhi isko explain kar le ek video mein
you are using prev pointer, it means it only valid for doubly linked list.
greatful
doesn't space complexity become O(n) for recursion since the function calls get stored in the call stack?
How is flattened linked list's head's next is set to NULL?
Hare Krishna!