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

[@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

[@SachinVerma-dw3mz]

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

[@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 ??

[@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

[@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!

[@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; }

[@saidurgasrividyaupadhyayul4675]

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

[@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?

[@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; }

[@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

[@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.

[@shaiksoofi3741]

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

[@madanmohanpachouly6135]

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

[@dhruvilbhuptani727]

This guy is a legend.

[@JKA-sf7ll]

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

[@lencywork6853]

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

[@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]

🅸'🅼 🅷🅰🅿🅿🆈

[@qindynamic]

your writing on the last is brilliant

[@selflearner8895]

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

[@KadenCasanave]

One of the greatest videos on youtube. Cheers.

[@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); }

[@aiknowledge-n2s]

Finally understood the mystery behind recursion of linked List Reversal.

[@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

[@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

[@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

[@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!

[@MadaraUchiha-c7q]

amazing and flawless explanation

[@ShravaniBhujbal-c7k]

one decade later, thanks for the help

[@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! :)

[@AmitYadav-og7ep]

Thank you brother for this simple explanation

[@discoverybyr3605]

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

[@pratikjha2742]

hope u reach 1 million soon

[@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.

[@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**

[@hardstuck170]

smartest thing i have ever seen

[@suyashsrivastava3671]

Well explained sir , recursion is sort of complicated.

[@kmlx19]

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

[@kushagragupta8460]

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

[@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; } }

[@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 ; }

[@annie157]

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

[@RohitKumar-eo9td]

You are an amazing teacher!! Hats Off!!

[@ajinkyakale4391]

Great explanation!

[@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.

[@CargoPantsDude]

Your tutorial has helped me a lot, thanks

[@sanskarkumar028]

very clear explaination thanku so much sir

[@HeyMr.OO7]

Legends Never Die ! 💙

[@hoerbschmidt618]

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

[@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

[@kyledrewes6552]

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

[@LunaFlahy]

awesome explanation!!!

[@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. }

[@rishabhhedaoo9926]

Yet again, Amazing !!

[@iamsksuthar]

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

[@thestarinthesky_]

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

[@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.

[@Bigini_]

great explanation, keep up the good work

[@mycodeschool]

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

[@SatyendraJaiswalsattu]

kzbin.info/www/bejne/a2a4nYywo5ifaac

[@asmereg]

best of all time

[@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

[@alamgirhossien4004]

I love this tutorial

[@arjunragu995]

Please help! you lost me at 6:10 marker! please explain how P is pointing at node 150? also once recursion is finished and last three lines begin, you set Node* q = p -> next; // q is pointing to nullptr and then you set q->next = p; but how can you set a nullptr to point to p?

[@arjunragu995]

so after 3 hours of trying to figure out how! It has come to my realization that once the stack begins to unwind it will "start" from Reverse(150) and not Reverse(250) because Reverse(250) was "completed" with the RETURN statement! Phew!! Thank you this is a wonderful video my friend!!

[@satyamlal4461]

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

[@shreyasshettigar5395]

Superb thank u

[@rachitmittal448]

**** Code for Linked List in C++ **** #include using namespace std; class Node{ public: int data; Node *next; Node(){ data = 0; next = NULL; } Node(int input){ data = input; next = NULL; } }; class Linked_List : public Node{ Node *head; int len; public: Linked_List(){ head = NULL; len = 0; } void Insert(int input){ Node *NewNode = new Node(input); if(head == NULL){ head = NewNode; len++; return; } Node *temp = head; while(temp->next != NULL){ temp = temp->next; } temp->next = NewNode; len++; } void Insert(int input, int position){ Node *NewNode = new Node(input); if(position == len){ Insert(input); len++; return; } if(position == 1){ NewNode->next = head; head = NewNode; len++; return; } if(position > len || position < 1){ cout next = (temp->next); temp->next = NewNode; len++; } void Print(){ Node *temp = head; if(head == NULL){ cout next = (temp->next)->next; delete deleted; } void Reverse(){ // Iterative Approach // Three Pointer Approach for Reversal Node *next, *prev, *current; current = head; prev = NULL; while(current != NULL){ next = current->next; current->next = prev; prev = current; current = next; } head = prev; } void Reverse_2(Node *p){ // Recursive Approach if(p->next == NULL){ // Exit Condition for Recursion head = p; return; } Reverse(p->next); // Recursive Call // Node Fix Node* q = p->next; q->next = p; p->next = NULL; } Node* GetHead(){ return head; } int GetLength(){ return len; } }; int main(){ Linked_List L1; L1.Print(); // output 'Empty linked list' L1.Insert(1); L1.Insert(2); L1.Insert(3); // L1.Insert(4); L1.Insert(5); L1.Insert(6); L1.Print(); // output the Linked list at this stage : 1 2 3 5 6 L1.Insert(4,4); L1.Print(); // 1 2 3 4 5 6 L1.Insert(4,9); // outputs Wrong Position cout

[@kautukraj]

Very helpful!

[@pradeepramola2295]

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

[@adityaojha2701]

You are amazing.

[@cheems08213]

Thank you Animesh!

[@jalajkhajotiaiitr]

Magnificent work. Thanks a lot for this :)

[@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.

[@unhappysisyphus]

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.

[@Karthik-yy6up]

Wow, very succinct. Thank you so much!

[@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; }

[@SanjayThakurMnit]

Thank you for this wonderful lesson

[@purubhatnagar483]

great video sir

[@GagandeepSingh-tl7zg]

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

[@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; }

[@manishtripathy1549]

Thanks... nice one. Made it simple.

[@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;

[@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

[@zachgosteady]

Thank you so much for these videos!

[@culesamericano9929]

the 4th one should be 150 not 100 right?

[@akhiladiga9771]

exactly

[@tomsmith9849]

shouldn't the node that holds 4 have its next link point to 150, not 100? Thanks, by the way, greats videos.

[@TheGinger852]

very clear, good, thanks man!

[@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

[@mannambhavani4266]

Thank you, tq, tq...

[@atharvakulkarni3007]

very informative video thanks

[@_babayaga_007_]

Shouldn't we also add ptr == NULL in the base case for all safety?

[@nischaykhanna9621]

great video there is only one issue the node with data 4 at address should point to 150 and not 100 . the code is correct just a writting error

[@harshadsindhav]

awesome explanation....thank you.

[@jaspreetsingh-cn2mb]

you do great man

[@simonzhai7881]

Thanks man! Good instruction!

[@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.

[@brocklesnarufcchamp1]

what does "head->next->next=head" exactly mean ?

[@aswathyjagadeesh]

Thank You Sir!!!