Reverse a linked list using recursion

[@bohotsaaridhop]

8 years later, still one of the best video to understand this topic.

[@sharcodes]

you will shock to know the creator of this channel is no more. I must Say he was Gems ans his content made him eternal.

[@dragonking1051]

@@sharcodesthe guy speaking in the video is alive but the other cofounder passed away. Because of that he stopped making these videos but he works at google now

[@durjoydc]

@@sharcodes The creator is alive and well. His friend and cofounder died in an unfortunate accident. He stopped making videos after that.

[@congdatt]

yes sir

[@nguaial8490]

Brilliant teaching on tough subject. On 6:50, the memory address of the right most node is 150.

[@voxflexx]

i was so confused

[@amruthachitluri4419]

yes

[@kirankasana2208]

me too

[@nitinmendiratta17]

Best videos on Data Structure. I am a masters student and all these videos seriously helped me for interview preparation. Please do post some more videos on Trees and Graphs and bit manipulation. Really appreciate your way of explanation

[@yadneshkhode3091]

bhai konsi company me ho ab muje lelo apke company me

[@redgamer6105]

He is no more so can't post.

[@Bouryal.Y]

@@redgamer6105 thank you!!

[@yashtailor1543]

Come back @mycodeschool❤❤😭😭😭😭😭

[@vedsinha9905]

He is dead

[@yashtailor1543]

@@vedsinha9905 yeah 😭

[@DexTech]

he is dead ????

[@gauti_]

@@DexTech Nope, he is working in google, one of other cofounder(humble fool) is dead.

[@DexTech]

@@gauti_ humble fool ??

[@SachinVerma-dw3mz]

11 years later , revising this topic from the videos feels nostalgic

[@ArhamShahhacker]

If anyone thinking that what if head pointer is not global then here's the code struct node* reverse(struct node* ptr){ struct node* head; if(ptr->next==NULL){ head=ptr; return head; } head=reverse(ptr->next); struct node* temp=ptr->next; temp->next=ptr; ptr->next=NULL; return head; }

[@rahulkumar0194]

Thankyou

[@prithvigupta8215]

Thank you

[@manfredoweber3562]

i checked one further on each call, that way you can get rid of temp node Node* reverse_r(Node * root, Node * out=NULL){ if(root->next->next==NULL){ out=root->next; root->next->next=root; } else{ out = reverse_r(root->next); root->next->next=root; root->next=NULL; } return out; }

[@mannyw_]

@@manfredoweber3562 This fails if the size of the LinkedList is 1

[@RealMcDudu]

You rock man! I was a little worried because of the accent that I won't be able to understand well, but you explain extremely well and clear. Kudos!

[@saidurgasrividyaupadhyayul4675]

Only video that explains how the call stack executes and reverses the links of the list...thanks for the explanation

[@shaiksoofi3741]

We are missing your content. You are such a good teacher

[@muhammednasir4722]

Hi, the way u are presenting the things really awesome...! I think this is the most easiest way to reverse a list. explanation: In the last recursive call previous will be last element in the list and that will be turned out to first (header). otherwise just change the next pointer to previous element. void List::reverse(Node* current,Node* previous) { if (current == NULL) { m_header = previous; return; } reverse(current->next,current); current->next=previous; }

[@madanmohanpachouly6135]

After watching so many video , got clarity here -- thank you for such a clean explanation.

[@KrittinKalra]

I tried solving this on my own before watching the video and this is what I came up with. The solution in the video is correct and mine works too. Some of you may find it useful. From the main(), I called reverse(head, NULL); void reverse(struct node* p, struct node * prev) { if(head==NULL) { return; } if(p->ptr==NULL) { head=p; return; } rev(p->next,p); p->next=prev; }

[@wandererstraining]

Amazing series of videos so far. I'm very thankful for its quality, and I hope that its author rests in peace. I had already done linked lists, but I had never used recursion on them. Brilliant. In order to better dive into the topics, I usually try to figure out a solution before watching videos or reading solutions in books. In this case, the solution I came up with did not presuppose a global pointer to the first node, so the function I created is fully self-contained: list * list_reverse(list *lst, list *prev) { list *head = NULL; if(lst != NULL) { head = list_reverse(lst->next, lst); lst->next = prev; } else { head = prev; } return head; } It takes two parameters: the first node (lst), and the previous node's pointer (prev), which would be NULL since the first node would not have any node prior to it. It returns a pointer to the new head of the list, the new first node. It creates a pointer named head that will be used to keep track of the first node. It verifies whether the node it received as a parameter is NULL. If it is not NULL, it calls itself recursively using its next element as the first node, and itself as the previous node, and changes the current node's next to the previous one provided as the prev parameter. (That means that the first node's next will become NULL.) If the lst parameter (current node) is null, the head pointer is changed to the previous node's address, or to NULL if it was the only node. After the if statement, the function returns the head pointer. That return of the head pointer is important, as it will be set when the end of the list is reached, and will be preserved as-is across the recursion. Example of usage: mylist = list_append(mylist, data1); mylist = list_append(mylist, data2); mylist = list_reverse(mylist, NULL); When using the function, the *prev parameter should always be NULL. If it is not, the list's last node's next pointer will point to whatever you chose, and the list will not end properly. Example of mistake: mylist = list_reverse(mylist, mylist); //

[@smrutiranjanrout974]

I guess u'r a teacher. Well explained.

[@lencywork6853]

thanks man i searched many videos on this topic but found yours's the best

[@JKA-sf7ll]

Jenny and this guy...Best teachers to learn coding..

[@dhruvilbhuptani727]

This guy is a legend.

[@rajeshroy2404]

Before watching the video, I tried to do it on my own and I did it. Guys first try it yourself by using your own logic and implementation. Then you will learn better. Here is my approach - // called reverseListUsingRecursion(NULL,head) in main() void reverseListUsingRecursion(Node* prev,Node* current){ if(current==NULL) return; Node *Current = current; Node *Next = current->next; current->next = prev; head = Current; reverseListUsingRecursion(Current,Next); } BTW this guy is the best teacher :).

[@koulicksadhu7679]

where are we printing brother?

[@KadenCasanave]

One of the greatest videos on youtube. Cheers.

[@selflearner8895]

Thank you so much ..... whenever I have a doubt in dsa I comeback to your channel....thank u again💗

[@dariom1171]

Code for C++: #include using namespace std; struct Node { int data; Node* next; }; Node* Insert(Node *head,int data) { Node *temp1 = new Node; temp1 -> data = data; temp1 -> next = nullptr; if (head == nullptr) head = temp1; else { Node *temp2= head; while(temp2 -> next != nullptr) { temp2 = temp2->next; } temp2 -> next = temp1; } return head; }; Node *RevRecursion(Node *head) { Node *temp1 = new Node; Node *temp2 = new Node; if (head->next == nullptr) { return head; } else { temp1 =RevRecursion(head->next); temp2 =head->next; temp2->next = head; head->next = nullptr; } return temp1; }; void Print(Node *p) { // Node *p is a local variable if (p==nullptr) return; //Exit condition cout data next); // Recursive call }; int main(){ Node *head = nullptr; // local variable head = Insert(head,2); // add node at the end of the list head = Insert(head,4); head = Insert(head,6); head = Insert(head,5);// List 2 Print(head); cout

[@latchmanakumar7404]

is there any way to avoid creating a new node temp1 in each recursive call(excluding global variables) in c/c++?

[@sarthakbhatia7639]

@@latchmanakumar7404 We can pass by reference head and it will update the same: #include using namespace std; struct node { int data; node *next; node(int data) { this->data = data; next = NULL; } }; void reverse(node **head, node *cur) { if (!cur || !cur->next) { *head = cur; return; } reverse(head, cur->next); cur->next->next = cur; cur->next = NULL; } void print_ll(node *head) { while (head) { cout data next; } cout next = new node(2); head->next->next = new node(3); head->next->next->next = new node(4); head->next->next->next->next = new node(5); head->next->next->next->next->next = new node(6); head->next->next->next->next->next->next = new node(7); cout

[@rohitjoshi6335]

Another approcah:: it will return new head pointer from main call :: Node* head = reverse(head, NULL); where pre is the previous node(which at start postioin is null); Node* reverse(Node* head, Node* pre){ Node* newNode; if(head == NULL){ newNode = pre; return pre; } Node* temp = head->next; head->next = pre; return reverse(temp, head); }

[@qindynamic]

your writing on the last is brilliant

[@codingandmathvideos]

Looking forward to when you will do graph algorithms and dynamic programming algorithms: MST, shortest path, LCS, Edit distance, longest common substring, longest palindromic substring, ...

[@amateurbeginner7538]

yeah man thats is right :)

[@parimal7]

still waiting Q.Q

[@avgspacelover]

@@parimal7 he passed away few years back

[@aiknowledge-n2s]

Finally understood the mystery behind recursion of linked List Reversal.

[@jabedhasan21]

We can reverse a linked list this way also. void reverseLinkedList(struct Node* prev, struct Node* curr) { if ( curr == NULL) { head = prev; return; } reverseLinkedList(curr, curr->next); curr->next = prev; } CALL -> reverseLinkedList(NULL, head); His explanation is really tremendous, No one can't recover your place. hats off humblefool

[@mycodeschool]

Thanks Jalaj !

[@powerfulwords6459]

🅸'🅼 🅷🅰🅿🅿🆈

[@TheKundan11]

Amazing explanation of Reversing Linked List using recursion. Such a nice use of algo. It was like watching TV inside TV inside TV and then coming out of it. Kudos to mycodeschool. Hats off ! Please answer a question of how Stack vs Heap works in Java which pure object oriented and donot uses pointers. Hoping to get your reply soon and eagerly waiting for more such videos.

[@aseembaranwal]

He could't reply back :(

[@kahaanparikh1013]

@@aseembaranwal zamn

[@MadaraUchiha-c7q]

amazing and flawless explanation

[@AmitYadav-og7ep]

Thank you brother for this simple explanation

[@Kartik-yv4cw]

At 6:45, the next of the 4th link should be set to 150, not 100. Minor correction. Otherwise, great video. :)

[@gurdyalsingh8228]

Kartik Singh yes..it is 150.

[@jayant9151]

Typo**

[@pratikjha2742]

hope u reach 1 million soon

[@UECDishaKhattri]

No existing explanations are better than yours. It would be great and really helpful if you consider YouTubing a part-time again.

[@muntahaislam1332]

Cool one! Thank you! Saved a lot lines!

[@kayveekhatrao2486]

Kuchh log chale jaate hain par aisi chhap chhor jaate hain ki maano aisa lagta hai jaise vo abhi bhi hamaarre biich hain. Stilll guiding me through your video lectures . _/\_ RIP

[@bhavananarayan8127]

One of the best videos on Data Structures! :)

[@ShravaniBhujbal-c7k]

one decade later, thanks for the help

[@kmlx19]

My god, this was so insightful haha. Thanks for the explanation

[@HeyMr.OO7]

Legends Never Die ! 💙

[@rohithkumarmiryala2083]

if head is not global variable, try this void Reverse(ListNode** A, ListNode* p){ if(p->next == NULL){ *A = p; return; } Reverse(A,p->next); p->next->next =p; p->next=NULL; } main(){ if(A==NULL) return A; Reverse(&A,A); return A; }

[@jmanaa9969]

You are a god mate, I was having a headache with the pointers but this worked perfectly.

[@suyashsrivastava3671]

Well explained sir , recursion is sort of complicated.

[@RohitKumar-eo9td]

You are an amazing teacher!! Hats Off!!

[@hardstuck170]

smartest thing i have ever seen

[@sanskarkumar028]

very clear explaination thanku so much sir

[@CargoPantsDude]

Your tutorial has helped me a lot, thanks

[@ajinkyakale4391]

Great explanation!

[@annie157]

You are a life saver Thank you so much for your this tutorials

[@bassammansour1361]

if you want to return the pointer Node, and use a local head struct Node* reverse (struct Node* p ){ static struct Node* head ; if( p->next==NULL ){ head = p ; return head ; } reverse ( p->next ); struct Node* Q = p->next; Q->next = p ; p->next = NULL ; return head ; }

[@shahirabdullah5438]

i wrote this way.......my function returns a node pointer and in main function the head is then assigned to the last node. like this ---- head = reverse_list_recursively(head); /*function code*/ node* reverse_list_recursively(node *cur) { if(cur->next == NULL) { return cur; } else { reverse_list_recursively(cur->next)->next = cur; return cur; } }

[@LunaFlahy]

awesome explanation!!!

[@iamsksuthar]

These videos are the best! :) Even a kid would come to know about DS! :)

[@kushagragupta8460]

would love to see mycodeschool do the data structures videos again and in cpp or python!

[@hoerbschmidt618]

great explanation how recursion works thanks to your drawing of the stack. Thank you very much!

[@kyledrewes6552]

This is a very clever trick. Thank you so much.

[@mycodeschool]

Thanks a lot Kundan, I have replied to your comment on other video.the idea of stack and heap as design concept for execution of programs is same in java also. We do not have pointer variables, but references pretty much work the same way. Its just that language does not give you freedom to see address in a reference variable and increment or decrement it which anyway is dangerous. The heap is totally managed in java. So, you do not have to bother up freeing up memory on heap.

[@arijitssongs7914]

mycodeschool plz make new videos...your videos are awsome nd it helps a lot

[@rishabhhedaoo9926]

Yet again, Amazing !!

[@jimwang4582]

Good tutorial,but i can not unstandard why p is 150 and q is 250?when recursion is finished,why p is not equal to 250?

[@rathnakaraum]

Python Ruby When exit condition is hit, recursive call Reverse(250) returns and entry of that call will be removed from stack. So, when the actual pointer adjustment starts the top record on stack is for Reverse(150) and hence p was 150

[@vishalhasija5910]

Thanks alott!

[@himanshuverma903]

p will be equal to 250 only if (p == NULL) because in this condition the last value will be passed to reverse function will be NULL due to which p=250 will be secured, instead of if(p->next == NULL) where the last value in reverse function is 250 due to which p=250 will not be secured and we get p=150. This all happens because the last call of the reverse function will return first in the if statement.

[@thestarinthesky_]

Great tutorial. Thank you. @6:46 it SHOULD be 150.

[@discoverybyr3605]

But there is mistake, when first second recursion(150) geting to be finished. There the value should be q=150 and p=0.

[@asmereg]

best of all time

[@Bigini_]

great explanation, keep up the good work

[@sidddddddoo7]

Actually we can achieve the same using fewer variables ( though at the cost of code readability ): struct node* reverse_ll_recursive(struct node *head){ if(head->next==NULL) return head; Node *q=reverse_ll_recursive(head->next); head->next->next=head; head->next=NULL; return q; // q stores value of the new head. }

[@alamgirhossien4004]

I love this tutorial

[@prekshakoirala7379]

This is awesome. But I think head moves everytime p->next == NULL holds true, which is kinda not what we want. Mycodeschool is my favorite though. superlike.

[@sergeyrar]

It doesn't move, since p->next= NULL is set after we return from the function call

[@pradeepramola2295]

Please god come back !!!! Can't believe what you taught exist lol seems impossible better than anything!!!!!

[@SanjayThakurMnit]

Thank you for this wonderful lesson

[@PiyushSingh-bi9kn]

void reverse(Node* current, Node* prev) { if (current->next == NULL) list = current; else reverse(current->next, current); current->next = prev; } call reverse(head, NULL) I dunno know, it just looks cleaner

[@adityaojha2701]

You are amazing.

[@kautukraj]

Very helpful!

[@raghureddy3237]

Another solution :: LNode* ReverseList1(LNode* head) { if (head == NULL) return NULL; if (head->next == NULL) { h = head; return head; } ReverseList1(head->next)->next = head; return head; } ReverseList1(head)->next=NULL;

[@cheems08213]

Thank you Animesh!

[@shreyasshettigar5395]

Superb thank u

[@mycodeschool]

contd.. I will try to get some video for Java also. :)

[@SatyendraJaiswalsattu]

kzbin.info/www/bejne/a2a4nYywo5ifaac

[@purubhatnagar483]

great video sir

[@SHUBHAMGI]

Node* Reverse(Node *head) { if(head == NULL) return head; if(head -> next == NULL) return head; Node * hs = Reverse(head -> next); head -> next -> next = head; head -> next = NULL; return hs; }

[@amateurbeginner7538]

is not working?

[@luciferplays9040]

It will work great

[@damilareoyebanji2834]

Great. Please at what point does hs gets affected

[@jalajkhajotiaiitr]

Magnificent work. Thanks a lot for this :)

[@Hreeshikesh]

You guys should upload the exact C/C++ code for better understanding I guess.

[@vedsinha9905]

He is dead brother

[@koulicksadhu7679]

@@vedsinha9905 wtf? How and when

[@SatyendraJaiswalsattu]

kzbin.info/www/bejne/a2a4nYywo5ifaac

[@manishtripathy1549]

Thanks... nice one. Made it simple.

[@Karthik-yy6up]

Wow, very succinct. Thank you so much!

[@atharvakulkarni3007]

very informative video thanks

[@harshadsindhav]

awesome explanation....thank you.

[@fjkldhakljf]

using double pointers without a global head : void ReverseRec(Node **ptrhead) { if ((*ptrhead)->next == NULL) { return; } Node *temp = *ptrhead; *ptrhead = (*ptrhead)->next; ReverseRec(ptrhead); temp->next->next = temp; temp->next = NULL; }

[@GagandeepSingh-tl7zg]

Java implementation continues: public void printReverseUsingRecursion(Node head) { if(head.next == null) return; printReverseUsingRecursion(head.next); System.out.println(head.next.data); }

[@pkj6962]

I thought why he inserted the statement p->next = NULL; because I thought we can substitute p->next with the next recursion. But the code was needed for the last node - that was first the head node.

[@TheGinger852]

very clear, good, thanks man!

[@jaspreetsingh-cn2mb]

you do great man

[@zachgosteady]

Thank you so much for these videos!

[@simonzhai7881]

Thanks man! Good instruction!

[@vikashtalanki]

I think we can code as below aswell public void recurReverse() { Node prev = null; Node curr = head; if(head==null || head.next==null) return; rReverse(prev,curr); } private void rReverse(Node prev,Node curr) { if(curr==null) { head = prev; return; } rReverse(curr,curr.next); curr.next=prev; }

[@mannambhavani4266]

Thank you, tq, tq...

[@AnonymousCoder7]

Legends Never Die ! 🤍

[@sammokkabasi8957]

Recursion uses a stack to store calls, so won't this approach take up O(n) memory? As compared to the iterative approach that only takes O(1) memory

[@ulneverno]

+Sammok Kabasi You're right, but its just in interview to check your level of thinking.

[@nguaial8490]

Iterative is O(n) since it is going through entire loop.

[@constructor365]

He was talking about space complexity.Iterative is O(1) in space complexity

[@amateurbeginner7538]

what is difference space and memory complexity?

[@lastofthestars6481]

The iterative approach does not take o(1) time.

[@ashupipalia6046]

nice bro..

[@satyamlal4461]

i think exit condition from recursion in revprint should be if(p->link==NULL) return;

[@VijayRajanna]

An initial check to see if "head" is NULL , is missing.

[@mycodeschool]

Vijay Rajanna - Good catch Vijay ! Thanks for noticing :)

[@abhisheksurwariya]

mycodeschool yes...and the address was also incorrect but thats minor

[@johndoe-eh2ol]

An error is an error, Abhishek. There are many people, who are just beginning to learn, who might not be smart enough to realise that. So stop acting smart!

[@gopikrishnans5815]

john doe it's good he pointed out. A beginner may be puzzled.

[@riyadshauk2432]

if (!p) return; // this should be the first statement of the function. If using NULL, can equivalently write "if (p == NULL) return;" This will only be true if the first node, also called the "head" is NULL. Otherwise (if the "head" is not NULL), "if (p->next == NULL)" will always be true before "if (p == NULL)" would ever be true.

[@sheezansultan1776]

lines below reverse(p->next); will never be executed!

[@HansNiemann762]

What ?

[@SatyendraJaiswalsattu]

kzbin.info/www/bejne/a2a4nYywo5ifaac

[@thavs]

YAS! YEAH YEI, i really need this

[@walddrygonzalez6234]

+Maria Lopez baia baia :v

[@aswathyjagadeesh]

Thank You Sir!!!

[@BCS_AnkurMishra]

def reverse_recurse(self, itr): if itr.next == None: self.head = itr return self.reverse_recurse(itr.next) itr.next.next = itr itr.next = None python code

[@Manikanta-zu9tm]

The 4th node address part should be 150(because the previous node address is 150)

[@saurabhshrivastava224]

Thanks,really.Gud one...